Formulas · Mathematics

Permutations and combinations

5 formulas, each with worked examples. Revision sheet · Practise these formulas

Class 11

Fundamental principle of counting

N = mn

What each letter means
$N$	the number of ways to do both things, one after the other
$m$	the number of ways to do the first thing
$n$	the number of ways to do the second thing, whatever the first choice was

If one thing can be done in m ways and, after it, a second thing in n ways, then the two together can be done in m × n ways.

Why it works

Each of the m first choices can be followed by any of the n second choices. That makes m rows of n, which is m × n ways in all.

When to use it

Counting outfits, meals, routes, codes, number plates and arrangements made one step at a time.

How to use it

Break the job into steps done one after another.
Count the ways for each step.
Multiply the counts. For more steps, keep multiplying.

To remember: "And" multiplies; "or" adds.

Other forms

To remember itFor three steps with p, q and r ways, the count is p × q × r, and so on for more steps.

Worked examples

Story

A lunch is one of 5 main dishes and one of 3 desserts. How many different lunches are there?

$5 \times 3 = 15$

Answer: 15

Picture

There are 4 roads from town A to town B and 3 roads from B to C. How many routes go from A to C through B?

$4 \times 3 = 12$

Answer: 12

Direct

How many outfits can be made from 3 shirts and 4 pairs of trousers?

$3 \times 4 = 12$

Answer: 12

Reverse

A shop can make 36 outfits from 4 shirts and some skirts. How many skirts does it have?

Try it first, then show the working

$4 \times 9 = 36$

Answer: 9

Exam

How many 3-digit numbers can be made from the digits 1, 2, 3, 4 and 5 if no digit is used twice?

Try it first, then show the working

The hundreds digit has 5 choices, then the tens digit 4, then the units digit 3.
$5 \times 4 \times 3 = 60$

Answer: 60

Common mistake: Adding when the steps both happen (one and then the other), or multiplying when they are alternatives (one or the other).

Class 11

Permutations of r things from n

^{n} P_{r} = \frac{n !}{( n - r )!}

What each letter means
$^{n} P_{r}$	the number of arrangements (permutations) of r things chosen from n different things
$n$	the number of different things to choose from
$r$	how many of them are arranged (r is at most n)

The number of ways to arrange r things in a row, chosen from n different things, is n! ÷ (n − r)!: n choices for the first place, n − 1 for the second, and so on for r places.

Why it works

By the counting principle the count is n × (n − 1) × (n − 2) × … × (n − r + 1), which is r numbers. Multiplying the top and bottom by (n − r)! turns that product into n! ÷ (n − r)!.

When to use it

When order matters: rankings, arrangements in a row, codes with no digit repeated, and posts such as captain and vice-captain chosen from a group.

How to use it

Check that the order matters and that nothing is used twice.
Multiply r numbers counting down from n, or work out n! ÷ (n − r)!.

To remember: Permutation: position matters.

Other forms

Special case $^{n} P_{n} = n!$ When all n things are arranged (r = n), since 0! = 1.
To remember itⁿPᵣ is r numbers multiplied, counting down from n: ⁷P₃ = 7 × 6 × 5.

Worked examples

Story

In how many ways can a club of 10 members choose a president, a secretary and a treasurer?

$\frac{10 !}{7 !} = 10 \times 9 \times 8$
$10 \times 9 \times 8 = 720$

Answer: 720

Picture

Six points are marked on a page. How many arrows can be drawn from one point to a different point?

An arrow is an ordered pair: a start and a different end.
$\frac{6 !}{4 !} = 6 \times 5$
$6 \times 5 = 30$

Answer: 30

Direct

Find ⁷P₃.

$\frac{7 !}{4 !} = 7 \times 6 \times 5$
$7 \times 6 \times 5 = 210$

Answer: 210

Reverse

If ⁿP₂ = 56, find n.

Try it first, then show the working

ⁿP₂ = n(n − 1) = 56, and 56 = 8 × 7, so n = 8.
$\frac{8 !}{6 !} = 56$

Answer: n = 8

Exam

How many 4-digit numbers can be made from the digits 1 to 9 if no digit repeats?

Try it first, then show the working

$\frac{9 !}{5 !} = 9 \times 8 \times 7 \times 6$
$9 \times 8 \times 7 \times 6 = 3024$

Answer: 3024

Common mistake: Using permutations when the order does not matter (a team, a hand of cards). Then it is a combination, and the answer is smaller.

Class 11

Arrangements with alike things

N = \frac{n !}{p ! q !}

What each letter means
$N$	the number of different arrangements
$n$	the number of things in all
$p$	how many are alike of one kind
$q$	how many are alike of a second kind (q = 1 when there is no second kind)

When some of the things are the same, swapping alike things makes no new arrangement. So divide n! by p! for a group of p alike things, and by q! for a second group.

Why it works

Label the alike things so they are all different: then there are n! arrangements. Each real arrangement appears p! × q! times among them (the ways to shuffle the labels), so n! = N × p! × q!.

When to use it

Arranging the letters of words with repeated letters (BANANA, MISSISSIPPI), beads or flags of the same colour, and shortest paths on a grid (so many steps right, so many up).

How to use it

Count all the things: n.
Count each group of alike things.
Divide n! by the factorial of each group's size.

To remember: Divide out the swaps you cannot see.

Other forms

Special case $N = \frac{n !}{p !}$ When only one kind of thing repeats (q = 1).
To remember itFor more kinds, keep dividing: n! ÷ (p₁! × p₂! × p₃! × …).

Worked examples

Story

5 red beads and 3 blue beads (the same apart from colour) are threaded in a row. How many patterns are possible?

$\frac{8 !}{5 ! 3 !} = 56$

Answer: 56

Picture

On a square grid, a path goes from one corner to the opposite corner in 4 steps right and 3 steps up. How many such shortest paths are there?

A path is an arrangement of 4 R's and 3 U's.
$\frac{7 !}{4 ! 3 !} = 35$

Answer: 35

Direct

How many different arrangements are there of the letters of BANANA?

There are 6 letters: A three times, N twice.
$\frac{6 !}{3 ! 2 !} = \frac{720}{12}$
$\frac{720}{12} = 60$

Answer: 60

Reverse

A word of 5 letters has one letter repeated and no other repeats. Its letters make 20 arrangements. How many times is the letter repeated?

Try it first, then show the working

5! ÷ p! = 20, so p! = 120 ÷ 20 = 6, and p = 3.
$\frac{5 !}{3 !} = 20$

Answer: 3 times

Exam

In how many ways can the letters of MISSISSIPPI be arranged?

Try it first, then show the working

11 letters: I and S appear 4 times each and P twice, so divide by 4!, 4! and 2!.
$\frac{11 !}{4 ! 4 ! 2 !} = 34650$

Answer: 34650

Common mistake: Dividing by the number of repeats instead of its factorial, or forgetting one of the groups.

Class 11

Combinations of r things from n

^{n} C_{r} = \frac{n !}{r ! ( n - r )!}

What each letter means
$^{n} C_{r}$	the number of ways to choose r things from n different things, when order does not matter
$n$	the number of different things to choose from
$r$	how many are chosen (r is at most n)

The number of ways to choose r things from n different things, when order does not matter, is n! ÷ (r! (n − r)!).

Why it works

Each choice of r things can be put in order in r! ways, so the arrangements ⁿPᵣ are r! times the choices. Dividing gives ⁿCᵣ = ⁿPᵣ ÷ r!.

When to use it

When order does not matter: teams, committees, hands of cards, choosing questions in an exam, handshakes, and lines through points.

How to use it

Check that the order does not matter.
Work out ⁿPᵣ and divide by r!, or use the factorial form.
Use ⁿCᵣ = ⁿCₙ₋ᵣ to make r small first.

To remember: A combination is a committee; a permutation is a podium.

Other forms

Same formula, another form $^{n} C_{r} = \frac{^{n} P _{r}}{r !}$ Arrangements divided by the r! orders of each choice.
Same formula, another form $^{n} C_{r} =^{n} C_{n - r}$ Choosing r to take is the same as choosing n − r to leave.

Worked examples

Story

A cricket team of 11 is picked from 14 players. In how many ways can it be picked?

Choosing 11 to play is choosing 3 to leave out.
$(11 14) = (3 14)$
$\frac{14 \times 13 \times 12}{3 \times 2 \times 1} = 364$

Answer: 364

Picture

Eight points lie on a circle. How many chords join pairs of them?

$\frac{8 \times 7}{2} = 28$

Answer: 28

Direct

Find ¹⁰C₃.

$\frac{10 !}{3 ! 7 !} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1}$
$\frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$

Answer: 120

Reverse

If ⁿC₂ = 45, find n.

Try it first, then show the working

n(n − 1) ÷ 2 = 45, so n(n − 1) = 90 = 10 × 9, and n = 10.
$\frac{10 \times 9}{2} = 45$

Answer: n = 10

Exam

A committee of 3 men and 2 women is chosen from 6 men and 5 women. In how many ways can it be chosen?

Try it first, then show the working

Choose the men in ⁶C₃ = 20 ways and the women in ⁵C₂ = 10 ways, and multiply.
$(3 6) \times (2 5) = 200$

Answer: 200

Common mistake: Using ⁿCᵣ when the order matters (ranks, posts, arrangements in a row). That is ⁿPᵣ.

Class 11

Pascal's rule

^{n} C_{r} +^{n} C_{r - 1} =^{n + 1} C_{r}

What each letter means
$n$	the number of things (a whole number)
$r$	how many are chosen (from 1 to n)

Two neighbouring numbers ⁿCᵣ₋₁ and ⁿCᵣ in one row of Pascal's triangle add up to the number ⁿ⁺¹Cᵣ just below them.

Why it works

To choose r things from n + 1, pick out one special thing. Either it is chosen, and the other r − 1 come from the remaining n (ⁿCᵣ₋₁ ways), or it is not, and all r come from the remaining n (ⁿCᵣ ways). The two cases never overlap and cover every choice, so they add.

When to use it

Building Pascal's triangle row by row, adding combinations quickly, and proving facts about them.

How to use it

Find two combinations with the same top number n and bottom numbers r − 1 and r.
Replace their sum with ⁿ⁺¹Cᵣ: the top grows by one and the bottom is the larger of the two.

To remember: Two above make the one below.

Other forms

Rearranged $^{n + 1} C_{r} -^{n} C_{r} =^{n} C_{r - 1}$ The choices that use the special thing.
To remember itIn Pascal's triangle each number is the sum of the two just above it.

Worked examples

Story

A class of 12 picks 4 students for a quiz team, and Asha is one of the 12. Count the teams with Asha and the teams without Asha, and check that together they make ¹²C₄.

With Asha, choose 3 more from the other 11: 165 teams. Without Asha, choose all 4 from the 11: 330 teams.
$165 + 330 = 495$
$(4 12) = 495$

Answer: 165 + 330 = 495 = ¹²C₄

Picture

Row 4 of Pascal's triangle is 1, 4, 6, 4, 1. Build row 5.

Each inside number is the sum of the two above it: 1 + 4 = 5, 4 + 6 = 10, 6 + 4 = 10, 4 + 1 = 5.
$4 + 6 = 10$
$(2 5) = 10$

Answer: 1, 5, 10, 10, 5, 1

Direct

Find ⁸C₃ + ⁸C₂ in one step.

$(3 8) + (2 8) = (3 9)$
$(3 9) = 84$

Answer: 84

Reverse

If ⁿC₄ + ⁿC₃ = ¹⁰C₄, find n.

Try it first, then show the working

By the rule the left side is ⁿ⁺¹C₄, so n + 1 = 10 and n = 9.
$(4 9) + (3 9) = (4 10)$

Answer: n = 9

Exam

Show that ⁿCᵣ + 2 ⁿCᵣ₋₁ + ⁿCᵣ₋₂ = ⁿ⁺²Cᵣ.

Try it first, then show the working

Split the middle term: (ⁿCᵣ + ⁿCᵣ₋₁) + (ⁿCᵣ₋₁ + ⁿCᵣ₋₂).
By the rule that is ⁿ⁺¹Cᵣ + ⁿ⁺¹Cᵣ₋₁, and by the rule again ⁿ⁺²Cᵣ.
A test with n = 5 and r = 3:
$(3 5) + 2 (2 5) + (1 5) = (3 7)$

Answer: Proved by using the rule twice

Common mistake: Adding numbers from different rows, or giving the answer the smaller bottom number r − 1.