Combinatorics
In the previous section you counted cases "by hand", reasoning each time about whether order mattered or elements were repeated. Combinatorics gives each of those situations a name and a fixed formula, so you don't have to reinvent the reasoning every time: you only need to identify what type of count it is. Think of Aoife and her friends trying to work out how many different ways they could pick a team for the school's camogie sevens, or how many codes a bike lock in Galway could have. In Leaving Cert language these are arrangements ($^nP_r$) and combinations ($^nC_r$). You will see how the lock one works out in the first section.
The multiplication principle and arrangements with repetition
A restaurant offers $4$ starters, $5$ main courses and $3$ desserts on its set menu. Calculate how many different complete meals (consisting of a starter, a main course…
A restaurant offers $4$ starters, $5$ main courses and $3$ desserts on its set menu. Calculate how many different complete meals (consisting of a starter, a main course and a dessert) a customer can order.
A digital bicycle lock is opened using a $4$-digit code (from $0$ to $9$). Determine how many different codes can be set if repeating digits is allowed.
A digital bicycle lock is opened using a $4$-digit code (from $0$ to $9$). Determine how many different codes can be set if repeating digits is allowed.
The standard vehicle registration system in Ireland (overseen by the RSA) assigns each vehicle a license plate consisting of a block of $4$ numerical digits followed by…
The standard vehicle registration system in Ireland (overseen by the RSA) assigns each vehicle a license plate consisting of a block of $4$ numerical digits followed by a block of $3$ letters. For the numbers, digits from $0$ to $9$ are used and can be freely repeated (from 0000 to 9999). For the letters, $20$ consonants of the alphabet are used (the five vowels are excluded to avoid acronyms or inappropriate words, as well as the Ñ and Q to avoid visual confusion with N and O or 0), and repetition is also allowed.
- a) Model the number of combinations provided by the numeric block and the alphabetic block using appropriate combinatorial tools, and deduce the total number of different license plates this system allows.
- b) According to registration statistics from the RSA and automotive industry associations, around $1.2$ million vehicles requiring this type of plate are registered annually in Ireland. Assuming a constant annual rate, estimate how many years it will take for the system to exhaust all its plates and assess whether the design is suitable for the Irish vehicle fleet in the medium and long term.
Arrangements without repetition: choosing and ordering
A robotics club has $12$ members. Determine how many different ways a committee consisting of a president, a vice president and a secretary can be chosen, given that no…
A robotics club has $12$ members. Determine how many different ways a committee consisting of a president, a vice president and a secretary can be chosen, given that no person can hold more than one position.
A security system requires a password consisting of $2$ distinct vowels followed by $3$ distinct digits (from $0$ to $9$). Calculate how many different passwords can be…
A security system requires a password consisting of $2$ distinct vowels followed by $3$ distinct digits (from $0$ to $9$). Calculate how many different passwords can be configured under these conditions.
Solve the following combinatorial equation to find the natural value of $n$: $3 \times V_{n, 3} = 4 \times V_{n-1, 3}$
Solve the following combinatorial equation to find the natural value of $n$:
$3 \times V_{n, 3} = 4 \times V_{n-1, 3}$
Arrangements of all $n$ elements ($n!$)
Circular arrangements and grid paths
When people sit round a circular table and rotations count as the same seating, fix one person's seat first. Then arrange the remaining $n-1$ people: $(n-1)!$.
A shortest path on a grid is a word made of moves, such as E and N. If a path needs $a$ moves East and $b$ moves North, the number of paths is $\dfrac{(a+b)!}{a!\,b!}=\binom{a+b}{a}$. To pass through a given point, multiply the paths for each stage.
Calculate how many different ways $6$ different textbooks can be arranged in a line on a shelf.
Calculate how many different ways $6$ different textbooks can be arranged in a line on a shelf.
Calculate the number of different anagrams, whether meaningful or not, that can be formed using all the letters of the word $INGENIERIA$.
Calculate the number of different anagrams, whether meaningful or not, that can be formed using all the letters of the word $INGENIERIA$.
Four men and four women are sitting down to dinner around a circular table. Determine how many different ways they can be seated if people of the same gender cannot sit…
Four men and four women are sitting down to dinner around a circular table. Determine how many different ways they can be seated if people of the same gender cannot sit next to each other (that is, men and women must alternate). Consider two arrangements to be identical if one can be obtained by rotating the other.
In a city whose streets form a perfect grid, calculate how many paths of minimum length exist to go from point $A(0,0)$ to point $B(6,5)$, passing through intersection…
In a city whose streets form a perfect grid, calculate how many paths of minimum length exist to go from point $A(0,0)$ to point $B(6,5)$, passing through intersection $C(3,2)$.
Combinations: choosing without ordering
You already know the binomial coefficient $\binom{n}{k}$ from the binomial theorem: in combinatorics it is written $^nC_r$ ("n choose r") and it counts the ways of choosing $k$ elements from $n$ when order does not matter.
Probability with combinations
When all outcomes are equally likely, $P(\text{event}) = \dfrac{\text{number of favourable outcomes}}{\text{number of possible outcomes}}$. If items are drawn at random without replacement and order does not matter, count both numbers with combinations. For parts of the sample, choose from each type separately and multiply.
A technology teacher needs to select $4$ students from a class of $20$ to attend a science fair. Calculate how many different groups of representatives can be formed.
A technology teacher needs to select $4$ students from a class of $20$ to attend a science fair. Calculate how many different groups of representatives can be formed.
$8$ points are marked on a plane, no three of which are collinear. Determine how many different straight lines can be drawn by connecting pairs of these points.
$8$ points are marked on a plane, no three of which are collinear. Determine how many different straight lines can be drawn by connecting pairs of these points.
From a deck of $40$ cards (four suits of ten cards, including four Kings), $3$ cards are drawn at random without replacement. Calculate the probability that all three…
From a deck of $40$ cards (four suits of ten cards, including four Kings), $3$ cards are drawn at random without replacement. Calculate the probability that all three cards are Kings.
In a chess tournament where each participant plays exactly one match against every other player, a total of $105$ matches were played. Determine the number of players…
In a chess tournament where each participant plays exactly one match against every other player, a total of $105$ matches were played. Determine the number of players who participated in the tournament.
Combinatorics with several groups and restrictions
In real problems it is useful to combine techniques: choosing $k$ from one group and $j$ from another (multiplying combinations), requiring some elements to stay together, or distributing elements among several destinations.
Together, "at least", labelled groups and sharing out units
Together: glue the elements that must be adjacent into one block, arrange the blocks, then multiply by the ways to order inside the block.
At least: either add the separate cases, or subtract the unwanted case from the total (the complement).
Labelled groups: choose the first group, then the second from those left, and so on, multiplying.
Sharing identical units: to share $m$ identical units among $k$ people (zero allowed) use $\binom{m+k-1}{k-1}$.
A biomedical research team must consist of $5$ people. The available candidates are $6$ biologists and $4$ chemists. Determine how many different teams can be formed if…
A biomedical research team must consist of $5$ people. The available candidates are $6$ biologists and $4$ chemists. Determine how many different teams can be formed if the team must contain exactly $3$ biologists and $2$ chemists.
Seven friends go to the cinema and sit in a row of $7$ seats. Two of them, Ana and Bruno, must sit next to each other. Calculate how many different ways they can occupy…
Seven friends go to the cinema and sit in a row of $7$ seats. Two of them, Ana and Bruno, must sit next to each other. Calculate how many different ways they can occupy the seats.
A tech company is going to form a cybersecurity committee of $6$ experts chosen from $8$ software engineers and $7$ network analysts. Calculate how many different…
A tech company is going to form a cybersecurity committee of $6$ experts chosen from $8$ software engineers and $7$ network analysts. Calculate how many different committees can be formed if there must be at least $4$ software engineers in the group.
An investor wishes to divide $10\,000$ euros among $4$ start-ups. If the investment in each company must be an exact multiple of $1\,000$ euros (including the…
An investor wishes to divide $10\,000$ euros among $4$ start-ups. If the investment in each company must be an exact multiple of $1\,000$ euros (including the possibility of investing $0$ euros in any of them), determine how many different ways the capital can be distributed.
The European Space Agency needs to assign $12$ astronauts to $3$ different space modules (Command Module, Lunar Module and Service Module). Calculate how many different…
The European Space Agency needs to assign $12$ astronauts to $3$ different space modules (Command Module, Lunar Module and Service Module). Calculate how many different ways the crew members can be distributed if each module must accommodate exactly $4$ astronauts.