Counting: which tool?
Permutation, combination, or neither? This page is a decision procedure for counting problems: the three questions that choose the tool, how to handle restrictions and repeated letters, when to count the opposite instead, and the binomial theorem term formula.
- 1. The three questions
- 2. The tools
- 3. Restrictions first
- 4. Cases and complements
- 5. Repeated items
- 6. The binomial theorem
The three questions
The idea: before any formula, answer three things about the situation. They pick the tool for you.
- Does order matter? Would swapping two chosen items give a different outcome? A president and a treasurer, yes. Two members of the same committee, no.
- Can items repeat? A PIN can reuse a digit; a seating plan cannot reuse a person.
- Are there restrictions? Must two people sit together, must a code start with a letter, must a committee include at least one girl?
| Order matters? | Repetition? | Use | Example |
|---|---|---|---|
| Yes | Yes | fundamental counting principle: multiply the choices | 4-digit PIN from 10 digits: 10⁴ |
| Yes | No | permutation ₙPᵣ = n!/(n − r)! | first, second and third from 8 runners: ₈P₃ = 336 |
| No | No | combination ₙCᵣ = n!/[(n − r)!r!] | a 3-person committee from 8: ₈C₃ = 56 |
The quick test: ₈P₃ is 6 times bigger than ₈C₃, because each group of 3 can be ordered 3! = 6 ways. If your answer is far too big, you probably counted orders that should not have been distinguished.
The tools
The idea: boxes for anything with positions, factorials for whole arrangements, and the two formulas for choosing from a larger group.
- Boxes. Draw one box per position and write how many choices that position has, then multiply. It handles restrictions naturally and is almost never wrong.
- n! arranges all n items: 7 people in a row is 7! = 5 040.
- ₙPᵣ arranges r of n items: 7 people into 3 chairs is ₇P₃ = 210.
- ₙCᵣ chooses r of n with no order: 3 of 7 people is ₇C₃ = 35.
- Add or multiply? Multiply for stages of one outcome ("and"), add for separate cases ("or").
Worked with boxes: 4-digit numbers from 1–7, no repeats, must be even
Start with the restricted position — the last digit must be 2, 4 or 6, so it has 3 choices. The remaining three positions are filled from the 6 unused digits: 6 × 5 × 4 = 120.
Total: 3 × 120 = 360. Filling the restricted box last is what goes wrong; do it first.
Restrictions first
The idea: deal with whatever is forced before you count anything free.
| Restriction | Technique | Example |
|---|---|---|
| Two people must sit together | glue them into one block, then multiply by the ways to order the block | 7 people, 2 together: 6! × 2! = 1 440 |
| Two people must not sit together | count all arrangements and subtract the together ones | 7! − 1 440 = 3 600 |
| A position is fixed | fill that box first, then the rest | codes starting with a vowel |
| Someone is excluded | reduce n for that position | a committee that cannot include the chair |
Watch out: when you glue people into a block, do not forget they can swap inside it. Missing the × 2! is the single most common counting error.
Cases and complements
The idea: "at least" and "at most" mean either several cases added together, or one subtraction. Pick whichever is shorter.
Worked: a committee of 4 from 6 boys and 5 girls with at least 3 girls
Cases: exactly 3 girls is ₅C₃ × ₆C₁ = 10 × 6 = 60. Exactly 4 girls is ₅C₄ = 5. Total 65.
Worked: the same committee with at least 1 girl
Four cases would work, but the complement is one line: all committees minus the all-boy ones.
₁₁C₄ − ₆C₄ = 330 − 15 = 315.
Rule of thumb: if "at least" leaves you with three or more cases, count the opposite instead. "At least one" is almost always a complement.
Repeated items
The idea: identical items make some arrangements indistinguishable, so divide by the factorial of each repeat.
Arrangements of all the letters of BANANA: 6 letters with 3 A's and 2 N's, so 6!/(3!2!) = 720/12 = 60.
The division is undoing overcounting: the three A's can be arranged 3! ways among themselves without changing the word, so every distinct arrangement was counted 3! × 2! = 12 times.
Repeats plus a restriction: arrangements of ALBERTA with the two A's apart
- All arrangements: 7 letters with A twice → 7!/2! = 2 520.
- A's together: glue them into one block → 6! = 720. No × 2! here, because the two A's are identical.
- Apart: 2 520 − 720 = 1 800.
The binomial theorem
The idea: in the expansion of (x + y)n, the general term is tk+1 = ₙCk xn−k yk. Every question is "find k, then substitute".
- The term number is k + 1, not k. The 4th term has k = 3.
- The exponents add to n in every term, which is a free check.
- Brackets matter: in (2x − 3)⁸, the "x" of the formula is 2x and the "y" is −3, so both the 2 and the minus sign are raised to powers.
Worked: the term containing x⁵ in (2x − 3)⁸
- General term: tk+1 = ₈Ck(2x)8−k(−3)k.
- Match the power: the power of x is 8 − k, so 8 − k = 5 and k = 3 — the 4th term.
- Substitute: ₈C₃(2x)⁵(−3)³ = 56 × 32x⁵ × (−27).
- Coefficient: 56 × 32 × (−27) = −48 384.
Dropping the 2⁵ or losing the sign on (−3)³ are the two ways this goes wrong.