DP IB Maths AA HL 1.7 – Permutations & Combinations

1.7.1 Counting Principles

• Fundamental Counting Principle (FCP)
– If one action can occur in $m$ ways and a second in $n$ ways, the pair can occur in $m\times n$ ways.
– Generalises to any number of successive, independent choices: multiply the counts for each stage.

• Why it matters
– Lets us analyse patterns, deal with very large numbers, and is the backbone of permutations/​combinations.
– Always decide whether choices CAN be repeated or must be distinct.

• AND vs OR logic
– Word “AND” ⇒ multiply.
– Word “OR” ⇒ add.
– Example (4 pens, 5 pencils)
• Pen AND Pencil ⇒ $4\times5=20$ ways.
• Pen OR Pencil ⇒ $4+5=9$ ways.

• Digit-repetition illustration
– 4-digit PIN, digits 0-9 with repetition: $10\times10\times10\times10=10^{4}=10000$.
– Without repetition: $10\times9\times8\times7=5040$.

• Worked example – Harry’s accessories
– 7 ties (T), 4 bow ties (B), 5 cufflinks (C).
a) Tie OR Bow tie OR Cufflinks ⇒ $7+4+5=16$ ways.
b) (Cufflinks) AND (Tie OR Bow tie) ⇒ $5\times(7+4)=5\times11=55$ ways.

• Examiner tip
– Counting-principle fluency is essential before tackling permutation/combination exam items.

Factorials

• Definition
– For non-negative integer $n$, $n!=n\times(n-1)\times\cdots\times2\times1$.
– By convention $0!=1$. (No objects can be arranged in exactly one way.)
– Negative arguments are undefined.

• Growth
– $5!=120\,,\;6!=720\,,\;10!=3\,628\,800$; numbers explode rapidly.
– Most handhelds overflow beyond roughly $70!$. Know your calculator’s limit & factorial key.

• Algebraic properties
– Cancellation: $\dfrac{n!}{(n-k)!}=n\times(n-1)\times\cdots\times(n-k+1)$.
– Useful identities
• $n!=n\times(n-1)!$ ⟹ $\dfrac{n!}{(n-1)!}=n$.
• $n!=n\times(n-1)\times(n-2)!$ ⟹ $\dfrac{n!}{(n-2)!}=n(n-1)$.
– Example: $\dfrac{8!}{5!}=8\times7\times6=336$ after cancelling.

1.7.2 Permutations

• Meaning
– A permutation counts the arrangements of objects where ORDER matters.

• All $n$ distinct objects
– Positions: $n,(n-1),(n-2),\ldots,1$ ⇒ $n!=nP_{n}$ permutations.
– Examples: $2! = 2\,(AB,BA);\;3! = 6\,(ABC,ACB,…)$.

• Selecting $r$ of $n$ objects (arranging a subset)
– FCP reasoning gives $n\times(n-1)\times\cdots\times(n-r+1)$ factors.
– Formula: $nP<em>{r}=\dfrac{n!}{(n-r)!}$. – Calculator key usually labelled nPr. – Illustrations • Arrange 3 of 5 ⇒ $5P</em>{3}=\dfrac{5!}{2!}=60$.
• Arrange 4 of 10 ⇒ $10P_{4}=5040$ (or $10\times9\times8\times7$).

• Permutations with restrictions

1. Items must remain together
   – Glue them into a single “super-item”.
   – Arrange the super-item + remaining objects, then internally arrange the glued items.
   – Multiply the two counts.

2. Items must not be consecutive
   – Total permutations – permutations where the forbidden items are together.
   – If >2 items must all be separate, seat the unrestricted items first, insert the others into gaps (use $nP_{r}$ on the gaps).

3. Specified positions (e.g.
   first/last, grouped colours)
   – Fix the compulsory places, then permute the rest.
   – If groups can swap sides, multiply by the number of ways the groups themselves can permute (often 2 or $g!$ for $g$ groups).

• Worked example – 9 tasks, 2 cannot be consecutive
– Total permutations: $9!=362\,880$.
– Force the two tasks to be a single block → 8 units. Arrangements with block together: $2!\times8!=80\,640$.
– Valid arrangements: $9!-2!\,8!=282\,240$.

• Language cues
– “Arrange”, “order”, “seat”, “place” ⇒ permutations.
– Watch for adjectives like “consecutive”, “alternate”, “at either end”, etc.

Combinations

• Concept
– A combination counts selections where ORDER is irrelevant.
– Choosing $r$ from $n$ without arrangement.

• Derivation
– Start from permutations ($nP<em>{r}$) and divide by the $r!$ ways each chosen subset could be ordered. – Formula: $nC</em>{r}=\dfrac{nP_{r}}{r!}=\dfrac{n!}{r!(n-r)!}$.
Calculator key: nCr or ${n\choose r}$.

• Key facts
– Binomial coefficients; appear in $(a+b)^{n}$ expansions.
– Edge values: $nC<em>{0}=nC</em>{n}=1$; reaffirm $0!=1$.
– Symmetry: $nC<em>{r}=nC</em>{n-r}$ (choose which ones to include or to exclude).

• When to add vs multiply in mixed questions
– Need A AND B: multiply counts.
– Need A OR B (mutually exclusive cases): add counts.
– Typical phrasing: “exactly”, “at least”, “no more than” will force you to break into cases, then add.

• Worked example – Oscar’s summer reading (4 F, 5 H, 2 C, choose 4)
i) 2 F + 2 H
– Ways = ${4\choose2}{5\choose2}=6\times10=60$.
ii) At least 1 of each type (need ≧1 F, ≧1 H, ≧1 C)
– Possible compositions & counts
• 1F 1H 2C → $\;{4\choose1}{5\choose1}{2\choose2}=20$
• 1F 2H 1C → $\;{4\choose1}{5\choose2}{2\choose1}=80$
• 2F 1H 1C → $\;{4\choose2}{5\choose1}{2\choose1}=60$
– Total = $20+80+60=160$.
iii) At least 2 fantasy
– Case split
• 2F + (0H 2C) ⇒ $6\times1=6$
• 2F + (1H 1C) ⇒ $6\times5\times2=60$
• 2F + (2H 0C) ⇒ $6\times10=60$  (Sub-total 126)
• 3F + 1H ⇒ ${4\choose3}{5\choose1}=4\times5=20$
• 3F + 1C ⇒ ${4\choose3}{2\choose1}=4\times2=8$
• 4F ⇒ ${4\choose4}=1$
– Grand total $=126+20+8+1=155$ ways.

• Examiner tips for combinations
– Look for verbs “choose”, “select”, “pick”.
– If question says “number of ways” without extra clues, examine whether order affects the outcome.
– Break “at least”/“at most” conditions into mutually exclusive cases; sum the results.

Quick Reference – Summary Formulae

• Fundamental Counting Principle → multiply successive choices.
• Permutation of all $n$ items → $n!$.
• Permutation of $r$ from $n$ → $nP<em>{r}=\dfrac{n!}{(n-r)!}$. • Combination of $r$ from $n$ → $nC</em>{r}=\dfrac{n!}{r!(n-r)!}$.
• Relations → $nC<em>{r}=\dfrac{nP</em>{r}}{r!}$, $nC<em>{r}=nC</em>{n-r}$.

Use these tools along with clear AND/OR logic and wording attentiveness to tackle any IB AA HL permutations & combinations problem confidently.