Combinatorial Proofs and Bijections

Master bijective proofs, double counting, and understand Catalan numbers.

24 min read
Advanced

Introduction

The most elegant proofs in combinatorics tell counting stories instead of manipulating algebra. Bijective proofs establish equality by constructing perfect correspondences.

Learning Objectives:

  • Construct bijective proofs
  • Use double counting techniques
  • Understand Catalan numbers

Bijective Proofs

Pascal's Identity

Prove combinatorially: (nk)=(n−1k−1)+(n−1k)\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}

Story: Choose kk people from nn, where person #1 is special.

  • Case 1: Person #1 is chosen → choose k−1k-1 from remaining n−1n-1 → (n−1k−1)\binom{n-1}{k-1}
  • Case 2: Person #1 not chosen → choose kk from remaining n−1n-1 → (n−1k)\binom{n-1}{k}

Total: (n−1k−1)+(n−1k)\binom{n-1}{k-1} + \binom{n-1}{k} ✓

python
from scipy.special import comb

def verify_pascal_identity(n, k):
    """Verify Pascal's identity"""
    lhs = int(comb(n, k, exact=True))
    rhs = int(comb(n-1, k-1, exact=True)) + int(comb(n-1, k, exact=True))
    return lhs, rhs, lhs == rhs

print("Pascal's Identity: C(n,k) = C(n-1,k-1) + C(n-1,k)")
print()
test_cases = [(5,2), (10,3), (20,8)]
for n, k in test_cases:
    lhs, rhs, valid = verify_pascal_identity(n, k)
    print(f"n={n}, k={k}: {lhs} = {rhs} {'✓' if valid else '✗'}")

Catalan Numbers

The Catalan Sequence

The nn-th Catalan number:

Cn=1n+1(2nn)C_n = \frac{1}{n+1} \binom{2n}{n}

Appears in:

  • Balanced parentheses strings of length 2n2n
  • Binary trees with nn nodes
  • Triangulations of (n+2)(n+2)-gon
  • Many more!

First few: 1, 1, 2, 5, 14, 42, 132, 429, ...

python
from scipy.special import comb

def catalan(n):
    """Compute nth Catalan number"""
    return int(comb(2*n, n, exact=True)) // (n + 1)

print("Catalan Numbers:")
for n in range(11):
    c_n = catalan(n)
    print(f"  C_{n} = {c_n}")

Key Takeaways

  1. Combinatorial proof: Tell a counting story
  2. Bijection: 1-to-1 correspondence shows equality
  3. Double counting: Same set, two ways
  4. Catalan numbers: Ubiquitous in counting problems

Next Part: Moving from Combinatorics to Probability Theory!

🎲

Combinatorics and Probability: From Counting to Inference

Master the mathematical foundations of counting, probability, and randomness. This comprehensive course bridges pure combinatorics with computational probability, covering everything from basic counting principles to advanced probabilistic methods, limit theorems, and real-world applications in algorithms, finance, and data science.