IB Analysis and Approaches HL · Probability · Section 1 of 5

Combinatorics and the fundamental counting principle

3 worked examples · By Álvaro López

Key idea

Combinatorics is the art of counting without listing. Before calculating probabilities with the Laplace rule you need to know how many cases there are, and there are almost always too many to write out. Everything comes down to two questions: does order matter? and can elements be repeated? The answer tells you which formula to use.

The fundamental counting principle

If a task is carried out in several successive stages and each stage can be done in several ways, without the number of options at one stage depending on the others, the total is obtained by multiplying.

Imagine making a sandwich by choosing 1 of 3 breads, 1 of 4 fillings and 1 of 2 sauces. Each bread can be combined with each filling, and each filling with each sauce, so there are $3 \cdot 4 \cdot 2 = 24$ possible sandwiches. When the options are alternatives (you do one thing or another, but not both) you add; when they are successive stages (you do one thing and then another) you multiply.

The factorial

To arrange $n$ distinct objects in a line, there are $n$ choices for the first, $n - 1$ for the second, and so on down to $1$ for the last. That product is written with the factorial:

So $5! = 120$ and $\frac{8 !}{6 !} = 8 \cdot 7 = 56$ : when dividing, almost everything simplifies, and that is what you should do on Paper 1.

The four situations

We start from $n$ distinct elements and form groups of $r$ of them. Depending on two questions there are four cases:

	Order matters	Order does not matter
Without repetition	Arrangements: $^{n} P_{r} = \frac{n !}{( n - r )!}$	Combinations: $(r n) = \frac{n !}{r ! ( n - r )!}$
With repetition	Arrangements with repetition: $n^{r}$	Combinations with repetition: $(r n + r - 1)$

The relationship between the two explains the formula. Each group of $r$ elements can be ordered in $r!$ ways, so the arrangements count each group $r!$ times:

$^{n} P_{r} = r! \cdot (r n) ⟹ (r n) = \frac{^{n} P _{r}}{r !}$

If all the elements are ordered ( $r = n$ ) we speak of permutations, and there are $n!$ .

With repetition

If each choice again has all $n$ options (a code of digits, a password of letters, rolling a die several times), at each stage there are $n$ possibilities and the product principle gives $n^{r}$ .

Combinations with repetition, $(r n + r - 1)$ , count groups of $r$ elements that may repeat and where order does not matter (for example, ways of choosing 5 scoops of ice cream from 3 flavours). They appear rarely; what is important to master is the choice between the other three cases.

Worked examples

Example 1 Basic

Recognising the type of grouping

Calculate in how many ways each of the following can be done.

a) Eight runners finish a race with no ties. Gold, silver and bronze medals are awarded.

b) From those same eight runners, three are chosen to form a relay team in which order is not distinguished.

c) A PIN of 4 digits is created, and each digit can be any of the ten, repeated or not.

d) Five different books are placed in a row on a shelf.

Solution

a) Order matters (gold, silver and bronze are different) and nobody is repeated: $n = 8$ , $r = 3$ .

$^{8} P_{3} = 8 \cdot 7 \cdot 6 = 336$

b) Now order does not matter: $n = 8$ , $r = 3$ .

$(3 8) = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56$

(Check: $336/3! = 56$ .)

c) With repetition and order, each of the 4 digits has 10 options: $1 0^{4} = 10000$ .

d) The 5 books are arranged: $5! = 120$ .

Answer: a) 336; b) 56; c) 10000; d) 120.

Example 2 Medium

A committee with conditions

An association has 7 men and 5 women. A committee of 4 people is chosen at random (roles are not distinguished).

a) How many different committees can be formed?

b) How many have exactly 2 women?

c) How many have at least one woman?

d) If instead a president and a secretary, different people, are chosen from the 12, in how many ways can this be done?

Solution

a) Choose 4 of 12 without order:

$(4 12) = \frac{12 \cdot 11 \cdot 10 \cdot 9}{4 !} = 495$

b) Stage 1: choose 2 women from 5, $(2 5) = 10$ . Stage 2: choose 2 men from 7, $(2 7) = 21$ . By the product principle:

$(2 5) (2 7) = 10 \cdot 21 = 210$

c) "At least one woman" is the opposite of "no women", that is, all 4 are men: $(4 7) = 35$ . Then

$495 - 35 = 460$

d) Now order matters (president and secretary are different posts) and there is no repetition: $^{12} P_{2} = 12 \cdot 11 = 132$ .

Answer: a) 495; b) 210; c) 460; d) 132.

Example 3 Hard

Conditions on two people and an equation

Seven friends, among them Ana and Beto, are going to pose for a photo.

a) In how many ways can the seven be arranged in a line?

b) In how many of these arrangements do Ana and Beto stand next to each other?

c) In how many do they not stand next to each other?

d) For a trip, a group of 4 is chosen from the seven friends. How many groups include Ana but not Beto?

e) A tournament has $n$ teams, and one match is played between each pair of teams (only once). 45 matches are played. Find $n$ .

Solution

a) All seven are arranged: $7! = 5040$ .

b) Treat Ana and Beto as a block. With the block and the other 5 friends there are 6 "objects" that can be arranged in $6! = 720$ ways. Within the block, Ana and Beto can swap places in $2! = 2$ ways:

$2 \cdot 6! = 1440$

c) Subtract from the total the cases in which they are together:

$5040 - 1440 = 3600$

d) Ana is in the group and Beto is not. Three places remain to be filled from the other $7 - 2 = 5$ friends, without order:

$(3 5) = 10$

e) Each match is a pair of teams, and order does not matter, so the number of matches is $(2 n)$ :

$\frac{n ( n - 1 )}{2} = 45 ⟹ n^{2} - n - 90 = 0 ⟹ (n - 10) (n + 9) = 0$

Since $n$ is positive, $n = 10$ .

In the exam: always state what you are counting (for example "block of 2 people, $6!$ orders, times $2!$ inside the block"). A numerical result without that justification may lose the method mark if one calculation fails. In problems with "not together" or "at least one", check that you use the complement: total minus unfavourable cases.

Common mistakes

Summary

Product principle: successive stages are multiplied; alternative cases are added.
$n! = n (n - 1) \dots 1$ and $0! = 1$ . Arranging $n$ distinct objects: $n!$ ways.
With order and without repetition: $^{n} P_{r} = \frac{n !}{( n - r )!}$ . Without order and without repetition: $(r n) = \frac{n !}{r ! ( n - r )!}$ . With repetition and with order: $n^{r}$ .
$^{n} P_{r} = r! (r n)$ and $(r n) = (n - r n)$ ; also $(2 n) = \frac{n ( n - 1 )}{2}$ .
To decide: does order matter? Are elements repeated? For "at least one" or "not together", count the total minus the opposite case.
In Paper 2, the GDC calculates $^{n} P_{r}$ and $(r n)$ ; still write the formula with its values.

Keep studying

Maths classes in Aldaia and online

Want to work on it together?

Free first consultation: we look at your level and your exam, and build a plan. Álvaro replies on WhatsApp.

Message us on WhatsApp