Combinatorics and Mathematical Induction
This domain asks you to count arrangements and selections correctly and to write a valid induction proof. Counting questions often hide a repetition or a circular arrangement; induction questions are marked on structure as much as on algebra.
Counting rules
If a task splits into stages with m and n choices, the total is m × n. The ordered count is nPr = n!/(n − r)! and the unordered count is nCr = n!/(r!(n − r)!), linked by nPr = nCr · r!. When objects repeat, divide by the factorial of each repetition: arrangements of n objects with p alike of one kind and q of another number n!/(p! q!). Circular arrangements of n distinct objects number (n − 1)!, and a garland or necklace where flipping is allowed numbers (n − 1)!/2.
Induction
The proof has three parts: verify the statement for the base value n₀; assume it true for n = k; use that assumption to derive the statement for n = k + 1. The middle assumption must actually be substituted in the final step, not merely announced.
Worked example
How many distinct arrangements do the letters of STATISTICS give? There are 10 letters, with S three times, T three times, I twice, and A and C once each. The count is 10!/(3! 3! 2!) = 3628800/72 = 50400.
Traps
- Using nCr when the order of selection matters.
- Forgetting to divide by the factorials of repeated letters.
- Omitting the base case, or failing to use the inductive hypothesis in the final step.
- Treating a necklace as an ordinary circle and dropping the factor ½.