Bijective Proof

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

To prove two counts are equal, build a bijection between the things they count. No algebra, no induction: if every object on the left pairs with exactly one on the right, the totals must match. It is the most honest kind of proof, because it explains why.

Counting one set two ways

Subsets of an n-element set correspond exactly to length-n binary strings: bit i says whether element i is in. There are 2ⁿ strings, so 2ⁿ subsets. Sort those subsets by size and you also get C(n,0)+C(n,1)+…+C(n,n). Two counts of one set, hence the identity.

Scheme

; Count subsets of {1..n} two ways.

; (1) by total: there are 2^n binary strings
(define (by-total n) (expt 2 n))

; (2) by size: sum of C(n,k) over all k
(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)))))

(define (by-size n)
  (let loop ((k 0) (s 0))
    (if (> k n) s (loop (+ k 1) (+ s (choose n k))))))

(display "2^5         = ") (display (by-total 5)) (newline)
(display "sum C(5,k)  = ") (display (by-size 5)) (newline)
(display "equal?      = ") (display (= (by-total 5) (by-size 5))) (newline)

Neighbors

🧮 Ch.2 Binomial Coefficients — the identity this chapter proves by counting
✎ Proofs — bijection is one of the cleanest proof techniques

← Binomial Coefficients · 2 of 10 by june.kim Inclusion–Exclusion · 4 of 10 →