Combinatorics
What this domain tests
Combinatorics on PEI Math 521B tests counting with justification: permutations and combinations, the pigeonhole principle, inclusion–exclusion, and binomial identities. The exam favors problems where the difficulty is choosing the right model, not performing arithmetic. Answers should identify whether order matters and whether repetition is allowed before any formula is applied.
Core rules and concepts
- Multiplication principle: if a task splits into independent stages with m and n choices, the total is mn.
- Permutations and combinations: ordered selections without repetition are n!/(n − r)!; unordered are C(n, r) = n!/(r!(n − r)!).
- Stars and bars: the number of nonnegative integer solutions to x₁ + … + x_k = n is C(n + k − 1, k − 1).
- Pigeonhole principle: placing more than kn objects into n boxes forces some box to hold at least k + 1. The generalized form uses ceiling functions.
- Inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|, extended by alternating sums for more sets.
- Binomial theorem: (a + b)^n = Σ C(n, k) a^(n−k) b^k, and C(n, k) = C(n, n − k).
Worked example
How many ways can 10 identical candies be distributed among 4 children so each child gets at least one? Let yᵢ = xᵢ − 1, where xᵢ ≥ 1. Then y₁ + y₂ + y₃ + y₄ = 10 − 4 = 6 with yᵢ ≥ 0. By stars and bars the count is C(6 + 4 − 1, 4 − 1) = C(9, 3) = 84. A direct check of the model: each distribution corresponds to arranging 6 stars and 3 bars, giving 9 positions with 3 chosen for bars. If instead the candies were distinct, the answer would require inclusion–exclusion over the "at least one" conditions, not stars and bars.
Traps that cost marks
- Using combinations when order matters, or permutations when it does not.
- Applying stars and bars to distinct objects; it counts distributions of identical items only.
- Forgetting to subtract the overlap in inclusion–exclusion, or mishandling the alternating signs for three or more sets.
- Stating the pigeonhole principle without identifying the boxes and objects explicitly, which weakens the proof.