Binomial Coefficients

Applied Combinatorics (CC BY-SA) · appliedcombinatorics.org

C(n,k) is the single most reused number in combinatorics. Pascal's recurrence C(n,k) = C(n−1,k−1) + C(n−1,k) builds the whole triangle from addition alone, and the binomial theorem says row n is exactly the coefficients of (x+y)ⁿ.

The triangle is just addition

Every interior entry is the sum of the two above it. That single rule, seeded with 1s on the edges, reproduces every binomial coefficient with no factorials at all.

Row sums and the binomial theorem

The entries of row n sum to 2ⁿ (the number of subsets of an n-set). Set x = y = 1 in the binomial theorem and that identity falls out for free.

Scheme

; Pascal's recurrence: no factorials, just addition
(define (choose n k)
  (cond ((or (< k 0) (> k n)) 0)
        ((or (= k 0) (= k n)) 1)
        (else (+ (choose (- n 1) (- k 1))
                 (choose (- n 1) k)))))

; build a full row
(define (row n)
  (let loop ((k 0) (acc '()))
    (if (> k n) (reverse acc)
        (loop (+ k 1) (cons (choose n k) acc)))))

(display "row 4 = ") (display (row 4)) (newline)        ; (1 4 6 4 1)
(display "sum   = ") (display (apply + (row 4))) (newline) ; 16 = 2^4
(display "row 6 = ") (display (row 6)) (newline)

Neighbors

🧮 Ch.3 Bijective Proof — why the row sum is 2ⁿ, proven by counting subsets
# Number Theory — Lucas' theorem reads C(n,k) mod p off the digits

← Counting Foundations · 1 of 10 by june.kim Bijective Proof · 3 of 10 →