src/math/counting.lisp

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