In a café in Galway, how many different meals can you order by combining a starter, a main course and a dessert? How many 7-digit passcodes could your mobile phone have? Writing out the complete list by hand would be absurd. Combinatorics is the branch of mathematics that counts without having to list everything: in the Leaving Cert you will need it constantly, especially in probability. This block gives you the basic tools.
The fundamental principle of counting
A restaurant offers 4 starters, 3 main courses and 5 desserts. To fix a complete menu you make one decision at each stage, and the decisions are independent of one another.
Practice★☆☆Not started
A restaurant offers a set menu with $4$ starters, $3$ main courses and $5$ desserts. How many different ways can a full three-course meal consisting of a starter, a main…
A restaurant offers a set menu with $4$ starters, $3$ main courses and $5$ desserts. How many different ways can a full three-course meal consisting of a starter, a main course and a dessert be ordered?
A bicycle brand manufactures a model that is available in $3$ different frame sizes, $5$ colours and with $2$ different types of brakes. How many different versions of…
A bicycle brand manufactures a model that is available in $3$ different frame sizes, $5$ colours and with $2$ different types of brakes. How many different versions of this bicycle model are on the market?
To protect a bicycle at high school, a combination lock with $3$ rotating wheels is used, each with the digits from $0$ to $9$. The owner states that the code cannot…
To protect a bicycle at high school, a combination lock with $3$ rotating wheels is used, each with the digits from $0$ to $9$. The owner states that the code cannot start with $0$ and that the three digits must be distinct from each other.
a) Before performing any exact calculations, intuitively estimate whether the total number of possible codes will be less than $300$, between $300$ and $700$, or greater than $700$. Briefly justify what your initial intuition is based on.
b) Model the situation using the multiplication principle and calculate the exact number of different codes that satisfy these conditions.
c) Check whether your initial estimate was correct and reflect on how the result changes if digits were allowed to be repeated (keeping the first digit different from $0$).
The multiplication principle also works when the number of options changes from one stage to the next, as long as you know how many remain on each branch. A tree diagram is the clearest way to see this.
Notice: after drawing a red ball, only 4 balls remain (2 red and 2 blue) for the second draw, because it is not replaced. The number of options in the second stage depends on what happened in the first. The tree shows every possible pair of draws, with the options reduced on each branch.
Practice★☆☆Not started
Draw the tree diagram for the experiment consisting of tossing a fair coin and then rolling a tetrahedral die (with its faces numbered from $1$ to $4$). How many…
Draw the tree diagram for the experiment consisting of tossing a fair coin and then rolling a tetrahedral die (with its faces numbered from $1$ to $4$). How many possible outcomes does this compound experiment have?
You can do it on paper and send a photo with your answer.
Two basketball teams, Alfa and Beta, play a best-of-$3$ playoff (the first team to win $2$ games qualifies). Draws are not possible. Draw the tree diagram with all…
Two basketball teams, Alfa and Beta, play a best-of-$3$ playoff (the first team to win $2$ games qualifies). Draws are not possible. Draw the tree diagram with all possible outcomes of the playoff. In how many different ways can the series of games unfold?
You can do it on paper and send a photo with your answer.
Look at the grid in the figure. A robot moves from point A to point B, moving only to the right or upwards along the grid lines. How many different paths can the robot…
Look at the grid in the figure. A robot moves from point A to point B, moving only to the right or upwards along the grid lines. How many different paths can the robot take to reach its destination?
As soon as a task consists of placing elements one by one and there is one fewer available at each stage, the same product always appears: $n \cdot (n-1) \cdot (n-2) \cdots 1$. Because of its importance it has its own name and symbol.
When a large factorial is divided by a smaller one, you do not need to expand either of them completely: almost everything cancels.
The same idea works with letters: $\dfrac{(x+2)!}{x!} = (x+2)(x+1)$, because $(x+2)! = (x+2)(x+1) \cdot x!$.
You can also go the other way: write a product in factorial notation. A product that runs all the way down to $1$ is just a factorial. A product that stops early is a quotient of two factorials: multiply and divide by the missing part.
Practice★☆☆Not started
Calculate the value of the following numerical expressions using the properties of factorials: $\frac{8!}{6!}$ $4! + 3!$
Calculate the value of the following numerical expressions using the properties of factorials:
If you have more pigeons than pigeonholes, at least one pigeonhole will contain two or more pigeons. It seems obvious, but it is a very powerful tool for proofs: it lets you guarantee that something repeats, without needing to find the specific case.
Practice★☆☆Not started
In a chest of drawers, there are loose socks of $3$ different colours (black, white, and blue). If there is a power outage and you take out socks in the dark, what is…
In a chest of drawers, there are loose socks of $3$ different colours (black, white, and blue). If there is a power outage and you take out socks in the dark, what is the minimum number of socks you must pull out to guarantee having at least one pair of the same colour?
In a secondary school, there are $400$ students enrolled. Justify mathematically why you can guarantee that at least two students share the same birthday. What is the…
In a secondary school, there are $400$ students enrolled.
Justify mathematically why you can guarantee that at least two students share the same birthday.
What is the minimum number of students needed at the school to guarantee that at least three of them share the same birthday? (Assume non-leap years of $365$ days).
$5$ points are chosen at random inside a square of side length $2\text{ cm}$. Prove, using the pigeonhole principle, that there will always be at least two points whose…
$5$ points are chosen at random inside a square of side length $2\text{ cm}$. Prove, using the pigeonhole principle, that there will always be at least two points whose distance apart is less than or equal to $\sqrt{2}\text{ cm}$. (Hint: divide the square into strategic regions).
Back to the start: If a password has 7 positions and in each one you can choose from the 10 digits (0 to 9), by the multiplication principle there are $10^7 = 10{,}000{,}000$ possible combinations.
Summary
Let's practice! 10 medium exercises in this section