Topic 6 of 8

Counting and combinatorics

Step 21 · Proofs and discrete maths topics

Count outcomes with the product and sum rules, choose between permutations and combinations, and use the pigeonhole principle and inclusion-exclusion.

Product and sum rules

If a task is a sequence of choices with a and then b options, there are a × b ways to do it: the product rule. If it is one choice from two separate groups of a and b options, there are a + b ways: the sum rule.

Example: Codes

How many 4-digit codes use the digits 0 to 9, with repeats allowed?

Four choices, each with 10 options.

Answer10⁴, which is 10,000

Example: Menus

A meal is one of 4 soups or one of 3 salads, then one of 5 mains. How many meals are there?

Starter: 4 + 3 = 7 options, by the sum rule.
Then 7 × 5, by the product rule.

Answer35

Permutations and combinations

A permutation is an ordered arrangement; a combination is an unordered selection. Choosing k of n things gives P(n, k) arrangements but only C(n, k) selections, because each selection can be ordered in k! ways.

P(n, k) = \frac{n!}{(n - k)!} \qquad \binom{n}{k} = \frac{n!}{k!\,(n - k)!}

Example: Order matters

8 runners race. In how many ways can gold, silver and bronze be awarded?

8 choices for gold, then 7 for silver, then 6 for bronze: 8 × 7 × 6.

Answer336

Example: Order does not matter

How many 3-person teams can be chosen from 8 people?

There are 336 ordered choices, and each team is counted 3! = 6 times.
336 ÷ 6 = 56.

Answer56

Example: Arranging letters

How many arrangements does BOOK have?

4! = 24 if the two O's were different.
Swapping the O's changes nothing, so divide by 2.

Answer12

Pigeonhole and inclusion-exclusion

The pigeonhole principle: if more than n objects go into n boxes, some box gets at least two. Inclusion-exclusion counts a union without double counting: |A ∪ B| = |A| + |B| − |A ∩ B|.

Example: Birth months

Show that among 13 people, two share a birth month.

13 people go into 12 months.

AnswerSome month holds at least two of them

Example: Divisible by 2 or 3

How many of the numbers 1 to 60 are divisible by 2 or 3?

30 are divisible by 2 and 20 by 3.
10 are divisible by both, that is, by 6.
30 + 20 − 10 = 40.

Answer40

Try it yourself

Work each one on paper first, then open the answer to check.

In how many ways can 5 books be arranged on a shelf?
Show answer
120
In how many ways can a president and a treasurer be chosen from 10 people?
Show answer
90
In how many ways can 2 people be chosen from 10?
Show answer
45
What is C(6, 3)?
Show answer
20
How many people guarantee that two share a day of the week?
Show answer
8
40 play football, 30 play tennis and 10 play both. How many play at least one?
Show answer
60