International Baccalaureate · DP 1: Analysis and Approaches HL
Counting
I
Counting Principles
I.1
The Product Rule and the Addition Rule
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.
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.
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
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\)? 
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?
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
Modelling a Draw from a Bag
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 balls
- 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".
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.
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.
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.
Skills to practice
- Recognising the Draw
II
Factorial Notation
II.1
Factorials
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!\).
\(\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!}\).
$$\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.
$$\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}$$
Skills to practice
- Evaluating Factorials without a Calculator
- Expressing Products in Factorial Form
III
Permutations
III.1
Ordered Selections with Repetition
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$$
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?
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
- Counting Ordered Selections with Repetition
III.2
Ordered Selections without Repetition
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)!}$$
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)?
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!\).
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?
This is the number of permutations of 100 guests, which is \(100! \approx 9.33 \times 10^{157}\).
Skills to practice
- Solving Problems with Arrangements and Permutations
III.3
Permutations with Restrictions
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?
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.
- 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\)?
- 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.
- 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
- Counting Arrangements with Restrictions
- Justifying Counts of Arrangements with Restrictions
IV
Combinations
IV.1
Unordered Selections without Repetition
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. 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)!}$$ 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)!}$$
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?
The order of the numbers does not matter, so this is a combination. The number of ways is \(\binom{49}{5} = 1,906,884\).
Proposition — First Values and Symmetry
For every natural number \(n\): \(\dbinom{n}{0} = \dbinom{n}{n} = 1\); for \(n \geq 1\), \(\dbinom{n}{1} = \dbinom{n}{n-1} = n\); for \(n \geq 2\), \(\dbinom{n}{2} = \dfrac{n(n-1)}{2}\). For \(0 \leq k \leq n\), $$\binom{n}{k} = \binom{n}{n-k}.$$
By counting. The only subset with \(0\) elements is \(\emptyset\), the only subset with \(n\) elements is \(E\) itself; the subsets with \(1\) element are the \(n\) singletons. Choosing a subset with \(k\) elements amounts to choosing the \(n - k\) elements left in the urn: the subsets with \(k\) elements and those with \(n - k\) elements correspond one to one, hence \(\dbinom{n}{k} = \dbinom{n}{n-k}\); in particular \(\dbinom{n}{n-1} = \dbinom{n}{1} = n\). Finally \(\dbinom{n}{2} = \dfrac{n(n-1)}{2!}\) by the formula.
Example
Compute \(\dbinom{20}{18}\) and \(\dbinom{50}{49}\) without a calculator.
By symmetry, \(\dbinom{20}{18} = \dbinom{20}{2} = \dfrac{20 \times 19}{2} = 190\) and \(\dbinom{50}{49} = \dbinom{50}{1} = 50\).
Skills to practice
- Evaluating Binomial Coefficients by Simplification
- Evaluating with a Calculator
- Solving Problems with Combinations
- Computing Binomial Coefficients
IV.2
Choosing the Counting Formula
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)!}\) |
Skills to practice
- Counting Poker Hands
IV.3
Counting by Cases and by the Complement
An Urn of Twenty Tokens
An urn holds twenty tokens: eight white tokens numbered \(0\), four white tokens numbered \(2\), five red tokens numbered \(7\) and three red tokens numbered \(5\). The tokens are twenty different objects, even when they bear the same number. Four tokens are drawn together. How many draws contain at least one red token? A draw is a subset with \(4\) elements of the \(20\) tokens, so there are \(\dbinom{20}{4} = 4845\) draws in all. But “at least one red” is not one object to count: it means “one red, or two, or three, or four”. Two roads are open: count the four cases separately and add them, or count the draws with no red token and subtract. 
Twenty tokens: eight red, twelve white
Twenty tokens: eight red, twelve white
Method — Counting in Different Cases
- Name the object (\(k\)-tuple, \(k\)-tuple of distinct elements, subset) and count the whole universe \(U\), the set of all the outcomes, with its formula.
- Split into disjoint cases when the condition depends on a kind of ball (a colour, a number): describe each case by “so many of this kind, so many of that kind”, count it with the multiplicative principle (a choice among each kind), then add the cases with the additive principle. Check that the cases are pairwise disjoint and that together they cover the condition. For ordered draws, the positions taken by each kind are one more choice to count.
- “At least one”: go through the complement. The draws with at least one ball of a kind are all the draws minus those with none of that kind: \(\Card{E} = \Card{U} - \Card{\overline{E}}\). One subtraction replaces several cases.
- A constraint on positions (a fixed first element, two elements side by side): satisfy the constraint first, then count the remaining choices, and multiply.
Example
Four tokens are drawn together from the urn of twenty tokens above (eight red, twelve white). - How many draws contain exactly two red tokens?
- How many draws contain at least one red token? Answer with the complement, then check by adding the cases.
- How many draws consist of four tokens bearing the same number?
A draw is a subset with \(4\) elements of the \(20\) tokens: \(\Card{U} = \dbinom{20}{4} = 4845\).
- Two red tokens among \(8\) and two white tokens among \(12\), the two choices being independent: \(\dbinom{8}{2} \times \dbinom{12}{2} = 28 \times 66 = 1848\) draws.
- Complement: the draws with no red token are the subsets with \(4\) elements of the \(12\) white tokens, \(\dbinom{12}{4} = 495\). Hence \(4845 - 495 = 4350\) draws contain at least one red token. Check by cases, one, two, three or four red tokens, pairwise disjoint: $$\binom{8}{1}\binom{12}{3} + \binom{8}{2}\binom{12}{2} + \binom{8}{3}\binom{12}{1} + \binom{8}{4} = 1760 + 1848 + 672 + 70 = 4350.$$
- Four disjoint cases, one per number: four \(0\) among \(8\), four \(2\) among \(4\), four \(7\) among \(5\), four \(5\) among \(3\), which is impossible and counts \(0\): $$\binom{8}{4} + \binom{4}{4} + \binom{5}{4} + 0 = 70 + 1 + 5 + 0 = 76 \text{ draws}.$$
Example
A committee of \(3\) people is chosen among \(7\) colleagues, but two of them, Ada and Bob, refuse to sit together. How many committees are possible? Answer by the complement, then by cases. 
A committee is a subset with \(3\) elements of the \(7\) colleagues: \(\dbinom{7}{3} = 35\) committees in all. Complement: the committees containing both Ada and Bob are completed by one of the \(5\) other colleagues, \(5\) committees; hence \(35 - 5 = 30\) committees are possible. By cases, neither of the two or exactly one of them: \(\dbinom{5}{3} + 2 \times \dbinom{5}{2} = 10 + 20 = 30\). The two roads agree.
Skills to practice
- Counting with Constraints
V
Counting and Probability
V.1
Probabilities by Counting
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.
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?
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} $$
Skills to practice
- Calculating Probabilities by Counting
- Calculating Probabilities by Counting with Technology
VI
Going further
Skills to practice
- Solving Problems without Technology
- Solving Counting and Probability Problems
- Quiz
Jump to section