Unit 2 CLO 1 4 lecture hours

Counting, Permutation & Combination

Four formulas cover this entire unit. The skill is not memorising them — it is deciding which one the question wants. This is the single most useful unit in the syllabus, because Unit 3, 4 and 5 all lean on it.

The one question that decides everything

Does the order of the chosen things matter?

  • YES (first place, second place, rank, password, committee with a chair) → permutation nPr
  • NO (just a group, a hand of cards, a selection, any order) → combination nCr
On this page
  1. Basic principle of counting (multiplication & addition)
  2. Pigeonhole principle
  3. Permutations (nPr)
  4. Combinations (nCr)
  5. Trigger words that flip the formula
  6. Binomial coefficients & Pascal's triangle
  7. Self-check

1. The Basic Principle of Counting

Multiplication rule — do this one, then that one

If a task is made of k separate steps, and step i can be done in nᵢ ways, then the whole task can be done in:

Multiplication rule Total ways = n₁ × n₂ × n₃ × … × nₖ
MULTIPLY along every path  ·  branches ADD at a single node 3 choices 3 sizes → 3 × 3 = 9 outcomes start 3 shirts Red Blue Green S M L S M L S M L 9 dots = 9 outfits. You multiplied — you never listed them all.
A tree diagram is a great safety net for small numbers. For anything above about 4 × 4, just multiply in your head.
Example — a 4-digit PIN from digits 0–9, no restriction

Each of the 4 positions independently has 10 options. Positions are ordered (the first digit is not the same as the fourth).

10 × 10 × 10 × 10 = 10⁴ = 10 000
10 000 PINs. Note nʳ = n×n×…×n (r times) — that is the same rule.
Example — "at least one" style with the addition rule

A lock has 3 buttons, each labelled 1, 2 or 3. A code of length 2 is pressed. How many codes are possible?

3 × 3 = 9   (3 choices for digit 1, 3 for digit 2)
9 codes: 11,12,13,21,22,23,31,32,33

Addition rule — this OR that (but not overlapping)

When a task can be finished in two or more different but mutually exclusive ways, you add instead of multiplying.

Addition rule Total = way 1 + way 2 + … + way k   (the ways must be disjoint)
Critical distinction

Multiply when you must do all the steps (AND). Add when you can pick one of several options (OR).

Overlapping case (counted twice): inclusion–exclusion, |A ∪ B| = |A| + |B| − |A ∩ B|. Subtract the double-counted part.

Example — counting a committee

A club has 5 men and 4 women. How many ways to pick a committee of 3 with at least one woman?

Bad approach (double counts): total committees − all-men = 9C3 − 5C3 = 84 − 10 = 74. ✓ correct, but harder.

Better (disjoint, add directly): split by exactly how many women:

1 woman, 2 men:  4C1 × 5C2 = 4 × 10 = 40
2 women, 1 man:  4C2 × 5C1 = 6 × 5 = 30
3 women:        4C3 × 5C0 = 4 × 1 = 4
40 + 30 + 4 = 74 committees — same answer, but the "case by number of women" method also works for "exactly one" questions.

2. The Pigeonhole Principle

The Pigeonhole Principle If you put p pigeons into h holes, and p > h,
then at least one hole contains more than one pigeon.

Named after the obvious fact that you cannot give 12 pigeons 10 separate holes. In counting problems it answers: "how many are enough to guarantee…?"

6 PIGEONS, 4 HOLES → A COLLISION IS UNAVOIDABLE hole 1 hole 2 hole 3 hole 4 collision! 2 pigeons, same hole 6 > 4, so pigeon 5 guarantees a shared hole
Generalised form: to guarantee k pigeons share a hole, you need h(k−1) + 1 pigeons.
Generalised pigeonhole principle To guarantee at least k objects in one box, you need h(k−1) + 1 objects in h boxes.
Example — "guarantee two people share a birthday"

Question: how many people must be in a room to guarantee two share a birthday?

h = 366 possible birthdays (ignore leap years)
h(2−1) + 1 = 366 × 1 + 1 = 367
367 people. (With 366 people they could all have different birthdays.)
Example — three sharing a birthday
h(3−1) + 1 = 366 × 2 + 1 = 733 people guarantee three share a birthday.
733
The recipe for every pigeonhole question
  1. Find the number of categories (holes) — usually the number of possible values.
  2. Decide how many you need in one category (k) — read the word "two", "three", "pair".
  3. Answer = h(k−1) + 1.
  4. If a specific k is not requested, it is almost always k = 2, giving h + 1.
Careful

"Guarantee" is the trigger word. If a question says "at least" or "must", that is pigeonhole. If it says "in how many ways could this happen", that is nPr or nCr, not pigeonhole.

3. Permutations (nPr) — order MATTERS

Arrange r things chosen from n distinct things ⁿP r = n! / (n − r)! = n(n−1)(n−2)…(n−r+1)
"Gold, Silver, Bronze" — swapping 1st and 2nd changes the answer 1st gold 2nd silver 3rd bronze Ram vs Shyam Ram, Shyam, Gita Gita, Ram, Shyam Shyam, Gita, Ram All three are DIFFERENT results → count with nPr, not nCr.
The position is part of the answer. That is exactly what "permutation" means.
Example — medals from 8 athletes

Give gold, silver and bronze to 8 athletes.

⁸P 3 = 8 × 7 × 6 = 336

Read it as slots: gold has 8 choices, silver has 7 left, bronze has 6 left.

336 ways
Example — a committee where position matters

From 9 men and 6 women, choose a chairman, a secretary and a treasurer. Roles are different, so order matters.

Chairman: 9 + 6 = 15 choices
Secretary: 14 left
Treasurer: 13 left
Total = 15 × 14 × 13 = 2730
2730. Notice we used the addition rule to get 15, then multiplication. Two rules in one question — completely normal.
Trick — write the slots

Do not try to remember the formula. Write the slots on a line and count the options above each one, then multiply. If a slot says "any" with no title, order is not important for that slot and you have an nCr instead.

Shortcuts worth knowing: nP1 = n, nP2 = n(n−1), nPn = n!.

4. Combinations (nCr) — order does NOT matter

Choose r things from n distinct things, order irrelevant ⁿC r = n! / [ r! (n−r)! ]
"Choose a 3-person committee" — all members are equal Ram Shyam Gita ONE result {Ram, Shyam, Gita} — order ignored, so this is 1 way, not 6. Why the division? Each nCr group is counted nPr = r! times in nPr, so divide by r!. ⁿCr = ⁿPr / r! — this identity links the two formulas and is worth quoting for marks.
Braces { } = a set, so order is gone. Round brackets ( ) = an ordered list, so order counts.
Example — choosing a committee

From 10 students, choose a 4-person committee.

¹⁰C 4 = 10! / (4! · 6!) = (10·9·8·7) / (4·3·2·1) = 5040/24 = 210
210 committees
Example — a hand of cards (why 5 out of 52 is nCr)

How many 5-card hands from a 52-card deck? Suit and rank order do not matter.

⁵²C 5 = 2 598 960
2 598 960 — the classic poker number. If the question said "in how many ways can you be dealt 5 cards and arrange them in a row", it would be ⁵²C 5 × 5! or ⁵²P 5.
Trick — the division by r!

Whenever you use nPr and then notice the r things are actually interchangeable, just divide by r!. That single move converts any permutation answer into a combination answer.

So: "I used nPr but the positions are identical → divide by r!."

Handy values to memorise

VALUES THAT FALL IN THE EXAM AGAIN AND AGAIN ⁿC 1 = n ⁿC 0 = 1 ⁿC n = 1 ⁿC ⁿ⁻¹ = n ⁿC 2 = n(n−1)/2 ⁿC ⁿ⁻² = n(n−1)/2 ⁿC r = ⁿC ⁿ⁻ʳ ¹⁰C 5 = 252 ⁵²C 5 = 2 598 960 ⁹C 4 = 126 ⁸C 3 = 56 ⁿC r = ⁿC ⁿ⁻ʳ is the symmetry you see in Pascal's triangle — left half mirrors right half.
If you memorise nothing else from this unit, memorise ⁿC 2 = n(n−1)/2 and ⁿC r = ⁿC ⁿ⁻ʳ.

5. Trigger Words — the real exam skill

The question says…What it really asksUse
"arrange", "in order", "rank", "first/second/third", "code", "password", "PIN", "committee with a chair"Order mattersnPr
"choose", "select", "select a committee", "group", "team", "hand of cards", "subset"Order does not matternCr
"at least one", "at least two"Split into cases, then addaddition rule + nCr
"no two", "not together", "all different"Subtract the excluded casestotal − bad
"guarantee", "must", "at least … share"Pigeonholeh(k−1)+1
"how many ways" + two independent choicesMultiply×
"either … or …"Mutually exclusive options+
"from a group of m men and n women"Split by gender, add the casesΣ (mCi × nCj)
Master example — "no two girls together"

Question: In how many ways can 4 boys and 3 girls sit in a row of 7 chairs such that no two girls sit together?

Step 1 — deal with the boys first. The boys are the "spacers":

⁴P 4 = 4! = 24   ways to arrange the boys

Step 2 — the gaps. 4 boys in a row create 5 gaps:

_ B _ B _ B _ B _   →  5 gaps, and each girl must take a different gap
BBBB ▫▫▫▫▫ gap 1gap 2gap 3gap 4gap 5

Step 3 — place the girls in 3 of those 5 gaps:

⁵P 3 = 5 × 4 × 3 = 60   (a girl in a gap = no two girls adjacent)

Step 4 — multiply:

4! × ⁵P 3 = 24 × 60 = 1440
1440 arrangements
The gap trick for "no two together" / "not together"
  1. Arrange the other group: n!
  2. Count the gaps: for m items in a row there are m + 1 gaps
  3. Put one of each into distinct gaps: P(m+1, k)
  4. Multiply

For a circle ("around a round table") the answer is (n−1)!, because rotations are the same. Fix one person first, then arrange the rest. Add reflections too if mirror images count as different.

6. Binomial Coefficients & Pascal's Triangle

Where they come from (a + b)ⁿ = Σ ⁿC r · aⁿ⁻ʳ bʳ    r = 0 … n

The binomial coefficient ⁿC r is the r-th term multiplier in the expansion of (a+b)ⁿ. The array of all of them is Pascal's triangle.

PASCAL'S TRIANGLE 1 11 121 1331 14641 15101051 1615201561 172135352171 18285670562881 n = 0n = 1n = 2 n = 3n = 4n = 5 n = 6n = 7n = 8 row index n element = ⁿC r Each number = the TWO numbers above it added together. Outer edges are always 1.
Row n of the triangle is the list ⁿC 0, ⁿC 1, …, ⁿC n. That is all Pascal's triangle is.
Example — expand (x + 2)⁴ using Pascal's triangle

Row 4 of the triangle is 1, 4, 6, 4, 1. Attach the powers of x and 2:

(x + 2)⁴ = 1·x⁴ + 4·x³·2 + 6·x²·2² + 4·x·2³ + 1·2⁴
        = x⁴ + 8x³ + 24x² + 32x + 16

Check: put x = 1 and the result must equal (1+2)⁴ = 81. 1 + 8 + 24 + 32 + 16 = 81 ✓

(x + 2)⁴ = x⁴ + 8x³ + 24x² + 32x + 16
Example — find a specific coefficient

Question: find the coefficient of x³y² in the expansion of (x + y)⁷.

Coefficient of x³y² = ⁷C 3 = ⁷C 2 (symmetry) = 7×6/2 = 21

Always draw the missing exponent: 3 + 2 = 5, but the total is 7, so there is also an implicit x²y⁰ term. The coefficient of the x³y² term is ⁷C 3 (choose which 3 of the 7 brackets give the x).

21
Trick — which index goes first?

In (a+b)ⁿ, the term with an−r br has coefficient ⁿC r. The exponent of b tells you the index r. If you get 21 vs 35 wrong, it is because you used r = 5 instead of r = 2. Because ⁷C 2 = ⁷C 5, always pick the smaller index — it is easier to compute.

Other useful recurrence

The two ends and the ratio ⁿ⁺¹C r = ⁿC r + ⁿC r⁻¹     and     (r+1) · ⁿ⁺¹C r+1 = (n−r) · ⁿC r

The first says "Pascal's rule" — build the next row from this one. The second lets you walk across a row without recomputing factorials.

Self-check

Open to see the answers

1. How many ways can 5 students be seated in a row? What if they sit around a round table?

Row: ⁵P 5 = 5! = 120
Round table: (5−1)! = 24 (rotations are the same, so fix one person)

2. How many people are needed to guarantee two were born in the same month?

h = 12 months, k = 2 → 12(2−1) + 1 = 13 people

3. How many ways to pick a captain and a vice-captain from 7 players? How many to pick a 2-player team?

Captain + vice: ⁷P 2 = 7 × 6 = 42 (roles differ → order matters)
Team: ⁷C 2 = 21 (equal members → order does not matter)
Relation between them: 42 = 21 × 2! ✓

4. Expand (a + 1)⁵ and find the coefficient of a².

Row 5: 1, 5, 10, 10, 5, 1
(a+1)⁵ = a⁵ + 5a⁴ + 10a³ + 10a² + 5a + 1
Coefficient of a² = ⁵C 3 = 10 ✓ (matches the table, confirming the index rule)
← BackUnit 1 · Relations & Functions