International Baccalaureate · MYP 5 Extended

Counting and Probability (Optional)

⌚ ~115 min ▢ 14 blocks ✓ 71 exercises ➣ Prerequisites : Probability

I Counting Principles

I.1 Basic Counting Principles

Going furtherbeyond the syllabus — click to explore

Counting is the process of finding out how many elements are in a finite set of objects. It began with the study of games of chance, where probability calculations—like finding the chance of winning—rely on counting outcomes. When all outcomes are equally likely, the probability of an event is simply the ratio of favourable outcomes to the total number of possible outcomes. This is why counting is a key skill in probability, but its uses go far beyond: it is essential in many areas of mathematics.
When we count on our fingers, we handle small sets. Counting methods handle sets that are far too large or too complicated for finger-counting.

Report an error

Method — Modelling a random draw from a bag

A bag problem represents a random draw of balls from a bag. The bag contains $n$ balls, each numbered from 1 to $n$, which are indistinguishable by touch, making the draw random.

Bag with 4 ballsThere are two key criteria to distinguish these draws:

The order in which the balls are drawn. If order matters, it’s a "draw with order"; if not, it’s a "draw without order". For example, drawing balls 7, 33, and 24 is written as $(7,33,24)$ with order and $\{7,33,24\}$ without order. Note that $\{7,33,24\} = \{33,24,7\}$, but $(7,33,24) \neq (33,24,7)$.
Replacement. If each ball is placed back in the bag before the next draw, it’s a "draw with replacement"; if not, it’s a "draw without replacement".

Proposition — Product rule

If there are $m$ different ways to do one thing, and for each of these, there are $n$ different ways to do another thing independently, the product rule says there are $m \times n$ ways to do both things in sequence.

Example

In a horse race with 10 horses, how many different ways can you bet on the top three finishers in exact order (triple forecast)? Model this as a draw from a bag.

Answer

This becomes: "How many ways can you draw 3 balls from a bag of 10 balls numbered from 1 to 10, with order and without replacement?"
For example, if the race results in horse number 3 finishing first, horse number 1 finishing second, and horse number 6 finishing third, this corresponds to drawing ball number 3 first, ball number 1 second, and ball number 6 third, written as $ (3,1,6) $. The product rule then counts these draws: $10 \times 9 \times 8 = 720$ possible bets.

Example

Three towns, $X$, $Y$, and $Z$, are connected by roads as shown. How many different ways can you travel from $X$ to $Z$ via $Y$?

Answer

For each of the 3 roads from $X$ to $Y$, there are 2 roads from $Y$ to $Z$. By the product rule, there are $3 \times 2 = 6$ different ways to travel from $X$ to $Z$ via $Y$.

Proposition — Addition rule

The addition rule states that if you have $n$ ways to do one thing and $m$ ways to do another, and the two cannot be done at the same time, then there are $n + m$ total ways to choose one of the actions.

Example

A person is going shopping at one store today, either in the north or south part of town. In the north, they can shop at a mall, a furniture store, or a jewellery store (3 options). In the south, they can shop at a clothing store or a shoe store (2 options).
How many different stores can they choose from?

Answer

By the addition rule, there are $3 + 2 = 5$ different stores to choose from.

Skills to practice

Applying the Product Rule
Applying the Addition Rule

I.2 Factorials

Going furtherbeyond the syllabus — click to explore

Definition — Factorial

For any integer $n \geq 1$, $n!$ (read as "$n$ factorial") is the product of the integers from $1$ to $n$: $$n! = n \times (n-1) \times \dots \times 2 \times 1.$$ By convention, we define $0! = 1$.

Example

Calculate $4!$.

Answer

$\begin{aligned}[t]4! &= 4 \times 3 \times 2 \times 1\\ &= 24\end{aligned}$

Proposition — A Product of p Decreasing Factors

For all natural numbers $n$ and $p$ with $0 \leq p \leq n$, $$n(n-1)(n-2) \dots (n-p+1) = \frac{n!}{(n-p)!}.$$ For $p = 0$ the product on the left is empty, equal to $1 = \dfrac{n!}{n!}$; for $p = n$ it is $n! = \dfrac{n!}{0!}$.

Proof

$$\begin{aligned}n(n-1)(n-2) \dots (n-p+1) &= \frac{n(n-1)(n-2) \dots (n-p+1)(n-p)(n-p-1) \dots 2 \times 1}{(n-p)(n-p-1) \dots 2 \times 1} \\ &= \frac{n!}{(n-p)!}\end{aligned}$$ for $1 \leq p \leq n - 1$: the numerator is completed into $n!$ by multiplying and dividing by $(n-p)(n-p-1) \dots 2 \times 1 = (n-p)!$. The cases $p = 0$ and $p = n$ are checked directly.

Example

Express $10 \times 9 \times 8 \times 7$ in factorial form.

Answer

$$\begin{aligned}10 \times 9 \times 8 \times 7 &= \dfrac{10 \times 9 \times 8 \times 7 \times 6!}{6!} \\ &= \dfrac{10!}{6!} \end{aligned}$$

Definition — Binomial Coefficient

For any integers $n \geq p \geq 0$, the binomial coefficient $\binom{n}{p}$ is defined as $$\binom{n}{p} = \frac{n!}{p!(n-p)!}$$

Skills to practice

Evaluating Without a Calculator
Evaluating with a Calculator
Expressing Products in Factorial Form
Evaluating by Simplification

II Three Kinds of Draws

II.1 Ordered Draws with Replacement

Going furtherbeyond the syllabus — click to explore

Definition — p-list

A p-list is a selection of $p$ elements from a set of $n$ elements where the order of selection matters and elements can be repeated. It can be represented as an ordered p-tuple where components may be identical. This corresponds to drawing $p$ balls from a bag of $n$ balls with replacement and with order.

Example

The pair $(1,1)$ is a 2-list from the set $\{1,2,3\}$. Note that $(1,2)$ is a different 2-list from $(2,1)$ because the order is different. In total, there are 9 2-lists from this set, as shown in the tree diagram: $(1,1)$, $(1,2)$, $(1,3)$, $(2,1)$, $(2,2)$, $(2,3)$, $(3,1)$, $(3,2)$, and $(3,3)$.

Proposition — Number of p-lists

The number of p-lists of $p$ elements from a set of $n$ elements is given by the formula:$$n^p$$

Proof

For the first element in the list, there are $n$ choices. Since elements can be repeated (with replacement), there are also $n$ choices for the second element, and so on for all $p$ elements. By the product rule, the total number of lists is $n \times n \times \dots \times n$ ($p$ times), which is $n^p$.

Example

How many different 4-digit PINs can be created using the digits 0 through 9?

Answer

Each digit can be any of the 10 options, and repetition is allowed. This is a 4-list from a set of 10. The number of possible PINs is $10^4 = 10,000$.

Skills to practice

Solving Real-World Problems with Repetition Allowed

II.2 Ordered Draws without Replacement

Going furtherbeyond the syllabus — click to explore

Definition — Arrangement

An arrangement is a selection of $p$ elements from a set of $n$ elements where the order of selection matters and elements cannot be repeated. It can be represented as an ordered p-tuple with distinct components. This corresponds to drawing $p$ balls from a bag of $n$ balls without replacement and with order.

Example

The pair $(1,3)$ is an arrangement of 2 elements from the set $\{1,2,3\}$. Note that $(3,1)$ is a different arrangement. In total, there are 6 arrangements of 2 elements from this set, as shown in the tree diagram: $(1,2)$, $(2,1)$, $(1,3)$, $(3,1)$, $(2,3)$, and $(3,2)$.

Proposition — Number of Arrangements

The number of arrangements of $p$ elements from a set of $n$ elements is given by the formula:$$_nP_p = \frac{n!}{(n-p)!}$$

Proof

For the first element, there are $n$ choices. Since elements cannot be repeated, there are $n-1$ choices for the second, $n-2$ for the third, and so on, down to $n-p+1$ choices for the $p$-th element. By the product rule, the total number of arrangements is $n \times (n-1) \times \cdots \times (n-p+1) = \frac{n!}{(n-p)!}$.

Example

In a horse race with 10 horses, how many different ways can you bet on the top three finishers in exact order (triple forecast)?

Answer

This is an arrangement of 3 horses from 10. The number of ways is $_{10}P_3 = \frac{10!}{(10-3)!} = 10 \times 9 \times 8 = 720$.

Definition — Permutation

A permutation is an arrangement of all $n$ elements of a set ($p=n$).

Example

The ordered triple $(1, 2, 3)$ is a permutation of the set $\{1, 2, 3\}$. In total, there are $3! = 6$ permutations of this set: $(1, 2, 3)$, $(1, 3, 2)$, $(2, 1, 3)$, $(2, 3, 1)$, $(3, 1, 2)$, and $(3, 2, 1)$.

Proposition — Number of Permutations

The number of permutations of a set of $n$ elements is $_nP_n = n!$.

Proof

This follows directly from the arrangement formula by setting $p=n$:$_nP_n = \frac{n!}{(n-n)!} = \frac{n!}{0!} = n!$.

Example

How many ways are there to seat 100 guests at 100 chairs for a wedding?

Answer

This is the number of permutations of 100 guests, which is $100! \approx 9.33 \times 10^{157}$.

Method — Counting Arrangements with Restrictions

A restriction puts a condition on the arrangement: a place kept for some objects, objects kept together, objects kept apart. The product rule still counts the arrangements, provided the choices are made in an order where the number of options at each step does not depend on the options chosen before.

Restricted places first: fill first the places that carry a condition (a given object at an end, a first digit that cannot be $0$, a last digit that must be even), then arrange the other objects in the other places, and multiply.
Objects together: glue the objects that must stand side by side into one block; arrange the block and the other objects, then multiply by the number of orders of the objects inside the block.
Objects apart: count the complement. The arrangements in which two given objects are not side by side are all the arrangements minus those in which they are side by side; in the same way, “not all together” is the complement of “all together”.
Cases: when the number of options for a place depends on an earlier choice (the digit $0$ may come last but not first), split the arrangements into disjoint cases, count each case, and add the counts with the addition rule.

Example

Seven different books, two of which are atlases, are placed in a row on a shelf. How many orders are possible:

with no restriction?
with an atlas at each end of the row?
with the two atlases side by side?
with the two atlases not side by side?

Answer

Call the atlases $A_1$, $A_2$ and the other books $b_1$, …, $b_5$.

An order is a permutation of the $7$ books: $7! = 5040$ orders.
Restricted places first: the two atlases take the two ends, in $2!$ orders; the $5$ other books fill the $5$ middle places, in $5!$ orders. By the product rule, $$\begin{aligned}[t]2! \times 5! &= 2 \times 120\\ &= 240 \text{ orders}.\end{aligned}$$
Glue the two atlases into one block. The block and the $5$ other books make $6$ objects, arranged in $6!$ orders; inside the block the atlases stand in $2!$ orders. By the product rule, $$\begin{aligned}[t]6! \times 2! &= 720 \times 2\\ &= 1440 \text{ orders}.\end{aligned}$$
Complement: the orders with the atlases not side by side are all the orders minus those with the atlases side by side. $$\begin{aligned}[t]7! - 6! \times 2! &= 5040 - 1440 &&\text{(parts 1 and 3)}\\ &= 3600 \text{ orders}.\end{aligned}$$

Example

Three-digit numbers are formed with the digits $0$, $1$, $2$, $3$, $4$, $5$, each digit used at most once; a number does not start with $0$. How many such numbers are there:

in all?
that are even?
that are greater than $300$?

Answer

Restricted place first: the hundreds digit is not $0$, so it has $5$ options; the tens digit then has $5$ options (the $0$ is allowed, the hundreds digit is used); the units digit has the $4$ digits left. By the product rule, $5 \times 5 \times 4 = 100$ numbers.
An even number ends with $0$, $2$ or $4$. The options for the hundreds digit depend on whether the $0$ is already used: two disjoint cases.
- Units digit $0$: the hundreds digit has $5$ options, the tens digit $4$: $5 \times 4 = 20$ numbers.
- Units digit $2$ or $4$ ($2$ options): the hundreds digit is neither $0$ nor the units digit, $4$ options; the tens digit has the $4$ digits left, $0$ included: $2 \times 4 \times 4 = 32$ numbers.
By the addition rule, $20 + 32 = 52$ even numbers.
A number greater than $300$ starts with $3$, $4$ or $5$ (the number $300$ itself would use the digit $0$ twice): $3$ options for the hundreds digit, then $5$ and $4$ options. $$3 \times 5 \times 4 = 60 \text{ numbers}.$$

Skills to practice

Solving Real-World Problems with Arrangements
Counting Arrangements with Restrictions
Justifying Counts of Arrangements with Restrictions

II.3 Unordered Draws without Replacement

Going furtherbeyond the syllabus — click to explore

Definition — Combination

A combination is a selection of $p$ elements from a set of $n$ elements where the order of selection does not matter. It can be represented as a subset of $p$ elements. This corresponds to drawing $p$ balls from a bag of $n$ balls without replacement and without order.

Example

The set $\{1,3\}$ is a combination of 2 elements from the set $\{1,2,3\}$. Note that $\{3,1\}$ is the same combination. In total, there are 3 combinations of 2 elements from this set: $\{1,2\}$, $\{1,3\}$, and $\{2,3\}$. Each combination corresponds to $2! = 2$ arrangements.

Proposition — Number of Combinations

The number of combinations of $p$ elements from a set of $n$ is given by the binomial coefficient:$$\binom{n}{p} = \frac{n!}{p!(n-p)!}$$

Proof

For any combination of $p$ elements, there are $p!$ ways to arrange them. Therefore, the number of arrangements ($_nP_p$) is equal to the number of combinations ($\binom{n}{p}$) multiplied by $p!$.$$_nP_p = \binom{n}{p} \times p! \implies \frac{n!}{(n-p)!} = \binom{n}{p} \times p!$$ Dividing by $p!$ gives the formula for combinations.

Example

How many different ways are there to choose 5 numbers for a Lotto draw from 49 numbers?

Answer

The order of the numbers does not matter, so this is a combination. The number of ways is $\binom{49}{5} = 1,906,884$.

Skills to practice

Solving Real-World Problems with Combinations

III Counting and Probability

III.1 Summary of Counting Formulas

Going furtherbeyond the syllabus — click to explore

This table summarizes the formulas for selecting $p$ elements from a set of $n$ elements.

	With Replacement	Without Replacement
Order Matters (p-list/Arrangement)	$n^p$	$_nP_p = \dfrac{n!}{(n-p)!}$
Order Does Not Matter (Combination)	$\text{(out of scope)}$	$\binom{n}{p} = \dfrac{n!}{p!(n-p)!}$

Report an error

Skills to practice

Counting Poker Hands

III.2 Applications to Probability

Going furtherbeyond the syllabus — click to explore

The primary motivation for developing the techniques of counting was to solve problems in probability. For an experiment where all outcomes are equally likely, the probability of an event $E$ is defined by the ratio of the number of favourable outcomes to the total number of possible outcomes.

Report an error

Method — Solving a Probability Problem with Counting

To find the probability of an event, follow these steps:

Identify the experiment: Determine what random process is taking place (e.g., drawing cards, rolling dice, selecting people).
Model the outcomes: Determine if the selection involves order and/or replacement. This will determine which counting formula to use. State that all the outcomes are equally likely (a random draw, fair dice, a well-shuffled deck): the formula of step 5 requires it.
Calculate the total number of outcomes ($\Card{U}$): Use the appropriate formula from the summary table to find the size of the sample space.
Calculate the number of favourable outcomes ($\Card{E}$): Define the event of interest and use the counting rules to find its size.
Calculate the probability: Apply the equiprobability formula, $P(E) = \frac{\Card{E}}{\Card{U}}$.

Example

In a horse race with 10 horses, you bet on the top three finishers in exact order (a triple forecast, or “tiercé”). All finishing orders being assumed equally likely, if you place one bet, what is the probability of winning?

Answer

The Method “Solving a Probability Problem with Counting” is applied in its five steps.

Identify the experiment: A race is run with 10 horses, an outcome is the ordered result of the top three finishers, and the event of interest is “this result matches the bet”.
Model the outcomes: We are selecting 3 horses from 10. All finishing orders are equally likely by assumption. Since the finishing order is exact, order matters. A horse cannot finish in more than one position, so this is without replacement. The model is an arrangement.
Calculate the total number of outcomes ($\Card{U}$): The total number of possible top-three finishes is the number of arrangements of 3 horses from a set of 10.$$ \Card{U} = {}_{10}P_3 = \frac{10!}{(10-3)!} = 10 \times 9 \times 8 = 720 $$ There are 720 possible outcomes for the top three positions.
Calculate the number of favourable outcomes ($\Card{E}$): To win, your bet must match the single correct finishing order. Therefore, there is only one favourable outcome.$$ \Card{E} = 1 $$
Calculate the probability: Using the equiprobability formula:$$ P(\text{Win}) = \frac{\Card{E}}{\Card{U}} = \frac{1}{720} $$

The probability of winning with a single bet is 1 in 720.

Skills to practice

Calculating Probabilities using Counting Principles

IV Going further

Skills to practice

Solving Counting Problems