Grades 9–12Discrete MathematicsPlanned

Combinatorics

Permutations and combinations, binomial coefficients and Pascal's triangle, the binomial theorem, the pigeonhole principle and inclusion–exclusion, with combinatorial proofs.

math.discrete.combinatorics

Show everything needed to reach this topic

The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.

Builds on

Counting principles Proof: direct, contrapositive, contradiction and induction Polynomials

Required prerequisites, all the way down: 15

You will learn to

Compute binomial coefficients and prove identities such as C(n, k) = C(n − 1, k − 1) + C(n − 1, k) by counting in two ways.
Prove and apply the binomial theorem.
Apply the pigeonhole principle and inclusion–exclusion to counting and existence problems.

Definition

C(n, k), read 'n choose k', is the number of k-element subsets of an n-element set.
Pigeonhole principle: if more than n objects are placed in n boxes, some box contains at least two objects.

Theorem

C(n, k) = n!/(k!(n − k)!) for 0 ≤ k ≤ n.
Binomial theorem: (x + y)ⁿ = Σ_{k=0}^{n} C(n, k) xᵏ yⁿ⁻ᵏ.
Σ_{k=0}^{n} C(n, k) = 2ⁿ.
Inclusion–exclusion: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Common misconceptions

Using permutations when order does not matter.
Thinking a pigeonhole argument must say which box contains two objects.

Leads to

Conditional probability and independence Recurrences and generating functions Graph theory

Optional discoveries

Enumerative combinatorics Generating functions turn counting problems into algebra.
← Systematic listing and counting