Counting Principles
Multiplication principle · Addition principle · Choosing the right approach
The multiplication principle
If one task can be done in \(m\) ways and a second independent task can be done in \(n\) ways, then both tasks together can be done in \(m \times n\) ways.
\(\text{Total} = n_1 \times n_2 \times n_3 \times \cdots\)
When to use ×: when you are filling multiple positions or making multiple independent choices. Think: "AND" → multiply.
Addition principle: if tasks are mutually exclusive ("OR"), add instead: Total = m + n.
How many 3-digit codes using digits 1–9 (repetition allowed)?
Each digit
9 choices for each of the 3 positions
Multiply
\(9 \times 9 \times 9 = 9^3\)
✓
729 codes
Ordered — matters
\(^nP_r\)
Use when POSITION matters. "Arrange 3 from 5" gives different results depending on order. ABC ≠BAC.
Unordered — doesn't
\(^nC_r\)
Use when only the SELECTION matters. "Choose 3 from 5" — {A,B,C} is same as {C,B,A}.
Key question
"Does order matter?"
Passwords/codes: YES. Committees/teams: NO. First/second/third place: YES. Just "select a group": NO.
Factorials
Definition · Key properties · Calculator key sequence · §10.1
Definition
\(n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1\)
0!= 1 (by definition)
1!= 1
5!= 120
10!= 3,628,800
Simplification trick: \(\dfrac{n!}{(n-r)!}\) — cancel the common tail. E.g. \(\dfrac{7!}{5!} = 7 \times 6 = 42\).
Casio Calculator — factorial key
fx-570ES PLUS & fx-991EX
Type 5
SHIFT
)
(the x! function)
=
→ 120
nPr and nCr: type n, then SHIFT → nPr or nCr, then r, then =
Arranging n distinct objects
\(n!\text{ ways to arrange }n\text{ distinct objects}\)
6 people can be seated in a row in \(6! = 720\) ways.
Permutations
Ordered selections · nPr formula · Special cases · §10.2
The formula
\(^nP_r = \dfrac{n!}{(n-r)!}\)
Number of ways to arrange \(r\) objects chosen from \(n\) distinct objects, where order matters.
\(^nP_r = n(n-1)(n-2)\cdots(n-r+1) \quad [r\text{ factors}]\)
Intuition: n choices for 1st position, (n-1) for 2nd, ..., (n-r+1) for rth. Multiply all.
How many ways to arrange 4 letters from {A,B,C,D,E,F}?
Identify
n=6, r=4, order matters → use \(^6P_4\)
Formula
\(^6P_4 = \dfrac{6!}{2!} = \dfrac{720}{2} = 360\)
Or
\(6 \times 5 \times 4 \times 3 = 360\)
✓
360 arrangements
Arrangements with identical items
\(\dfrac{n!}{p!\, q!\, r!\, \cdots}\)
Arrange n items where p are identical of one type, q of another, etc. Divide out the repeated arrangements.
Arrangements of MISSISSIPPI (11 letters: M×1, I×4, S×4, P×2): \(\dfrac{11!}{1!\,4!\,4!\,2!} = 34650\)
Circular permutations
When arranging n people in a circle, one position is fixed (no "start"), so we only arrange the remaining (n-1).
\(\text{Circular arrangements} = (n-1)!\)
Necklace/bracelet: if flipping the arrangement gives the same result (e.g. a necklace), divide further by 2: \(\dfrac{(n-1)!}{2}\)
6 people seated at a round table
Fix one
Fix one person as reference point
Arrange rest
Arrange remaining 5: \((6-1)! = 5! = 120\)
✓
120 circular arrangements
Combinations
Unordered selections · nCr formula · Pascal's triangle connection · §10.3
The formula
\(^nC_r = \binom{n}{r} = \dfrac{n!}{r!(n-r)!}\)
Number of ways to select r objects from n distinct objects where order does NOT matter.
\(^nC_r = \dfrac{^nP_r}{r!}\)
Intuition: take all permutations and divide by r! to remove ordered duplicates.
Symmetry: \(^nC_r = ^nC_{n-r}\). Choosing 3 from 10 = choosing 7 from 10 (same groups).
A committee of 4 chosen from 9 people
Order?
No — committee members are equal → combinations
Formula
\(^9C_4 = \dfrac{9!}{4!\,5!} = \dfrac{9\times8\times7\times6}{4\times3\times2\times1}\)
Calculate
\(= \dfrac{3024}{24} = 126\)
✓
126 committees
Useful identities
\(^nC_0 = ^nC_n = 1\)
\(^nC_1 = n\)
\(^nC_r + ^nC_{r+1} = ^{n+1}C_{r+1}\) (Pascal's rule)
\(\sum_{r=0}^{n} ^nC_r = 2^n\)
Interactive — nPr & nCr Calculator
—
Pascal's Triangle (first 8 rows)
Arrangements with Restrictions
Must include / must exclude · Items together · Items apart · §10.4
Strategy for restriction problems
- Deal with restricted items first — place the constrained people/objects, then fill the remaining spaces
- Items that MUST be together — treat them as a single block. Arrange the block + other items, then arrange within the block
- Items that must NOT be together — Total arrangements − arrangements where they ARE together (complementary counting)
- At least / at most problems — often easier via complementary counting
A and B must sit together in a row of 5 people
Block
Treat {A,B} as one unit → 4 units to arrange: \(4! = 24\) ways
Within block
A and B can swap: \(2! = 2\) ways
✓
\(4! \times 2! = 24 \times 2 = 48\)
A and B must NOT sit together (row of 5)
Total
\(5! = 120\) (unrestricted)
Together
From above: 48 arrangements where A,B are adjacent
✓
\(120 - 48 = 72\) arrangements
Committee of 3 from 5 men and 4 women — at least 1 woman
Complement
At least 1 woman = Total − (0 women)
Total
\(^9C_3 = 84\)
0 women
\(^5C_3 = 10\) (all men)
✓
\(84 - 10 = 74\)
Practice Questions
3 Easy · 3 Medium · 3 Hard — Permutations & Combinations
Easy 1
[2] Evaluate \(^8P_3\) and \(^8C_3\).
SOLUTION
P
\(^8P_3 = 8\times7\times6 = \boldsymbol{336}\)
C
\(^8C_3 = \dfrac{336}{3!} = \dfrac{336}{6} = \boldsymbol{56}\)
Easy 2
[2] How many ways can 5 people sit in a row of 5 chairs?
SOLUTION
Arrange
\(5! = 5\times4\times3\times2\times1 = \boldsymbol{120}\) ways
Easy 3
[2] A team of 3 is chosen from 7 people. How many ways?
SOLUTION
Select
Order doesn't matter: \(^7C_3 = \dfrac{7!}{3!\,4!} = \boldsymbol{35}\)
Medium 1
[4] How many 4-digit numbers can be formed from 1,2,3,4,5,6 if no digit is repeated and the number is even?
SOLUTION
Units digit
Even: must end in 2, 4, or 6 → 3 choices
Remaining 3
Choose 3 from remaining 5 digits in order: \(\,^5P_3=60\)
Total
\(3\times60=\boldsymbol{180}\)
Medium 2
[4] A committee of 4 is formed from 6 men and 5 women. Find the number of committees with at least 2 women.
SOLUTION
2W+2M
\(^5C_2\times^6C_2 = 10\times15 = 150\)
3W+1M
\(^5C_3\times^6C_1 = 10\times6 = 60\)
4W
\(^5C_4 = 5\)
Total
\(150+60+5=\boldsymbol{215}\)
Medium 3
[3] In how many ways can the letters of BANANA be arranged?
SOLUTION — repeated letters
Count repeats
B:1, A:3, N:2. Total 6 letters.
Formula
\(\dfrac{6!}{3!\cdot2!}=\dfrac{720}{12}=\boldsymbol{60}\)
Hard 1
[5] 8 people sit at a round table. How many arrangements are there if two specific people must NOT sit next to each other?
SOLUTION — complementary counting
Total circular
\((8-1)!=7!=5040\)
Subtract: together
Treat the pair as one unit: \(7\) objects in circle \(=(6)!=720\). The pair can swap: \(\times2=1440\)
Answer
\(5040-1440=\boldsymbol{3600}\)
Hard 2
[5] Find the coefficient of \(x^3\) in the expansion of \((2+x)^7\).
SOLUTION — Binomial Theorem
General term
\(T_{r+1}=\binom{7}{r}(2)^{7-r}(x)^r\). For \(x^3\): \(r=3\)
Coefficient
\(\binom{7}{3}\cdot2^4=35\times16=\boldsymbol{560}\)
Hard 3
[6] Find the term independent of \(x\) in the expansion of \(\left(2x-\dfrac{3}{x^2}\right)^9\).
SOLUTION
General term
\(T_{r+1}=\binom{9}{r}(2x)^{9-r}\left(\dfrac{-3}{x^2}\right)^r=\binom{9}{r}2^{9-r}(-3)^r x^{9-r-2r}=\binom{9}{r}2^{9-r}(-3)^r x^{9-3r}\)
Set power to 0
\(9-3r=0\Rightarrow r=3\)
Answer
\(\binom{9}{3}2^6(-3)^3=84\times64\times(-27)=\boldsymbol{-145152}\)
Past Year Paper Questions
Cambridge 0606 — P&C & Binomial
0606
[10]
(a) Find the number of ways 6 books can be arranged on a shelf if 2 specific books must be together. [3]
(b) Find the coefficient of \(x^2\) in the expansion of \((3-2x)^5\). [3]
(c) Find the values of \(n\) for which the coefficient of \(x^2\) in \((1+x)^n\) equals 15. [4]
(b) Find the coefficient of \(x^2\) in the expansion of \((3-2x)^5\). [3]
(c) Find the values of \(n\) for which the coefficient of \(x^2\) in \((1+x)^n\) equals 15. [4]
FULL SOLUTION
(a)
Glue the pair: 5 objects, \(5!=120\) arrangements, pair can swap: \(\times2=\boldsymbol{240}\)
(b)
\(T_3=\binom{5}{2}(3)^3(-2x)^2=10\times27\times4x^2=\boldsymbol{1080}x^2\)
(c)
\(\binom{n}{2}=\dfrac{n(n-1)}{2}=15\Rightarrow n(n-1)=30\Rightarrow n^2-n-30=0\Rightarrow(n-6)(n+5)=0\Rightarrow\boldsymbol{n=6}\)
0606 Style
Number Arrangements
[8]
A 4-digit number is formed using the digits 2, 3, 5, 7, 8 (no repetition).
(a) How many such numbers are there? [2]
(b) How many are even? [3]
(c) How many are greater than 5000? [3]
(a) How many such numbers are there? [2]
(b) How many are even? [3]
(c) How many are greater than 5000? [3]
FULL WORKED SOLUTION
(a)
Choose and arrange 4 from 5: \(P(5,4)=5\times4\times3\times2=\boldsymbol{120}\)
(b)
Last digit must be 2 or 8 (2 choices). Remaining 3 digits from 4: \(P(4,3)=24\). Total: \(2\times24=\boldsymbol{48}\)
(c)
First digit must be 5, 7, or 8 (3 choices). Remaining: \(P(4,3)=24\). Total: \(3\times24=\boldsymbol{72}\)
0606 Style
Combinations with Constraints
[7]
A team of 4 is chosen from 5 students from Year 11 and 4 students from Year 12.
(a) Find the number of possible teams with no restrictions. [2]
(b) Find the number of teams with at least 2 Year 12 students. [4]
(c) One specific Year 11 student refuses to work with one specific Year 12 student. How many valid teams are there? [1] (Using total minus restricted approach.)
(a) Find the number of possible teams with no restrictions. [2]
(b) Find the number of teams with at least 2 Year 12 students. [4]
(c) One specific Year 11 student refuses to work with one specific Year 12 student. How many valid teams are there? [1] (Using total minus restricted approach.)
FULL WORKED SOLUTION
(a)
\(\binom{9}{4}=\boldsymbol{126}\)
(b)
Exactly 2 Y12: \(\binom{4}{2}\binom{5}{2}=6\times10=60\)
Exactly 3 Y12: \(\binom{4}{3}\binom{5}{1}=4\times5=20\)
Exactly 4 Y12: \(\binom{4}{4}=1\)
Total: \(\boldsymbol{81}\)
Exactly 3 Y12: \(\binom{4}{3}\binom{5}{1}=4\times5=20\)
Exactly 4 Y12: \(\binom{4}{4}=1\)
Total: \(\boldsymbol{81}\)
(c)
Teams with both the conflicting pair: \(\binom{7}{2}=21\). Valid teams: \(126-21=\boldsymbol{105}\)