;               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))))