src/math/counting.lisp

   1
   2 ;V factorial V
   3 ;V    n!     V
   4 (defun factorial (n)
   5   (declare (fixnum n))
   6   (loop :for prod = 1 :then (* prod i)
   7         :for i :from 2 :to n
   8         :finally (return prod)))
   9
  10 ;V permutation V
  11 ;V     n!      V
  12 ;V  --------   V
  13 ;V  (n - r)!   V
  14 (defun nPr (n r)
  15   (declare (integer n r))
  16   (loop :for k :from (- n r) :to n
  17         :for prod = 1 :then (* prod k)
  18         :finally (return prod)))
  19
  20 ;V combination V
  21 ;V     n!      V
  22 ;V ----------  V
  23 ;V r!(n - r)!  V
  24 (defun nCr (n r)
  25   (declare (fixnum n r))
  26   (/ (nPr n r) (factorial r)))
  27
  28 ;V  assemblage  V
  29 ;V (r + n - 1)! V
  30 ;V ------------ V
  31 ;V  r!(n - 1)!  V
  32 (defun nAr (n r)
  33   (declare (fixnum n r))
  34   (nCr (1- (+ n r)) r))
  35