; n!
; n C k = -------------
; k! (n - k)!
;
; This algorithm uses only integer arithmetic, and is based on the
; observation that if we have multiplied j consecutive integers, their
; product has j as a factor. This code performs one needless division;
; eliding it is left as an exercise for the reader. Forcing k to be
; less than ceiling(n/2) reduces the number of iterations that this
; loop takes; it is not necessary for correctness.
(define (choose n k)
(let ((k (if (> k (+ 1 (quotient n 2))) (- n k) k)))
(let loop ((n n) (j 1) (r 1))
(if (<= j k)
(loop (- n 1) (+ j 1) (/ (* r n) j))
r))))