Permutations and Combinations · Lesson 1 of 6
Counting Choices in Stages
“Count arrangements and choices by organising a task into stages and separate cases.”
• Identify the stages that determine one complete outcome. • Apply the multiplication principle to two or more choices. • Distinguish choices with repetition from choices without repetition. • Count a restricted position first when it simplifies the reasoning. • Add counts for separate, non-overlapping cases.
Counting without writing every possibility
Imagine a four-wheel suitcase lock. Each wheel displays a digit from 0 to 9. You remember that the first digit is 7 and that the four digits in the correct code are different. Rather than write a long list of possible codes, we can organise the remaining choices. The same idea works for outfits, signals, letter arrangements and numbers.
One outcome means one complete result of the task. For the lock, it is a full ordered code, not an individual digit. A code ending in 123 is different from one ending in 132. Before counting anything, describe exactly what makes two outcomes different and whether an object may be used again.
The multiplication principle
Suppose you choose one of three pairs of trousers and one of two shirts. For each trouser choice, both shirt choices remain available. Each first choice therefore produces two complete outfits, and the three first choices produce three groups of two outfits.
Label the trousers P1, P2 and P3 and the shirts S1 and S2. The outfits are P1–S1, P1–S2, P2–S1, P2–S2, P3–S1 and P3–S2. Listing this small example makes the structure visible: the total is 3 × 2 = 6, rather than 3 + 2. An outfit needs both items, so we count pairs of choices.
If a task has successive stages, with m choices at the first stage and n choices at the second stage for each first-stage choice, there are m × n complete outcomes.
The choices at a later stage may depend on what has already been chosen. Multiplication still works when the number of available choices is the same for every path reaching that stage. If different paths give different counts, split the task into suitable cases first. The principle is about counting paths, and does not require a probability assumption of independence.
Problem
Choose one of 2 bags, one of 3 lunch boxes and one of 2 water bottles. How many sets are possible?
- 1.Choose the bag: 2 possibilities. For either bag, choose the lunch box: 3 possibilities. This produces 2 × 3 = 6 bag–box pairs.
- 2.For every pair, choose either bottle. There are 6 × 2 = 12 complete sets.
- 3.A three-stage branching diagram would have 2 first branches, 3 branches from each of those, and 2 final branches from each pair. Its 12 endpoints represent the sets.
Repetition changes the available choices
When an object has been used, ask whether it remains available. Arranging a fixed collection of different letters uses each letter at most once. Creating a code from an alphabet may allow the same letter again. These are different tasks even if they use the same symbols.
Problem
How many four-letter strings can be made from R, O, S and E, first without repetition and then with repetition?
- 1.Without repetition, the first position has 4 choices. After choosing a letter, only 3 remain; then 2 remain; then 1 remains.
- 2.Multiply the position counts: 4 × 3 × 2 × 1 = 24. The strings need not be meaningful words.
- 3.With repetition, choosing a letter does not remove it from later positions. Every position has 4 choices, so there are 4 × 4 × 4 × 4 = 256 strings.
Problem
The first digit of a four-digit lock code is 7. All four digits are different. How many remaining sequences might need checking?
- 1.The second digit can be any of the other 9 digits, including 0. A lock code may contain a zero in any position.
- 2.The third digit has 8 choices because 7 and the second digit are unavailable. The fourth has 7 choices.
- 3.There are 9 × 8 × 7 = 504 possible completions. This is the maximum number of distinct candidates, not a claim that all must be checked before success.
Problem
Four different flags are available. How many signals use two flags, one above the other?
- 1.Choose the upper flag in 4 ways, then choose the lower flag in 3 ways. A physical flag cannot be used twice in the same signal.
- 2.The count is 4 × 3 = 12. Exchanging the upper and lower flags creates a different signal, so order matters.
Choose the useful counting order
Counting stages need not follow the physical order in which symbols are written. A restricted position often makes the best first stage. Fill it in your reasoning first, then count the choices for the remaining positions.
Problem
How many even two-digit numbers can be made from 1, 2, 3, 4 and 5 when repetition is allowed?
- 1.An even number must end in 2 or 4. Count the units position first: 2 choices.
- 2.The tens position may contain any of the 5 digits, including the one already used. It therefore has 5 choices in either units case.
- 3.There are 2 × 5 = 10 numbers. Counting tens first without tracking the even condition would hide the restriction.
Adding separate cases
Sometimes a complete result can have one of several lengths or group compositions. Such alternatives cannot all occur in the same outcome. Count the stages within each case by multiplication, then add the counts across cases.
Problem
Five different flags are available. A signal uses at least two flags on a vertical staff. How many signals can be made?
- 1.The possible lengths are 2, 3, 4 and 5. These cases are separate because one signal has only one length.
- 2.Two flags give 5 × 4 = 20 signals. Three give 5 × 4 × 3 = 60. Four give 5 × 4 × 3 × 2 = 120. Five give 5 × 4 × 3 × 2 × 1 = 120.
- 3.Add the cases: 20 + 60 + 120 + 120 = 320. No signal is counted twice, and every allowed length has been included.
Multiply when a complete outcome requires successive choices. Add when you are combining separate alternatives. Before adding cases, check that they do not overlap and that together they include every allowed outcome.
Quiz
There are 4 jackets and 3 scarves. How many jacket–scarf pairs are possible?
Three positions use digits 1–5 with repetition allowed. How many strings are possible?
Three positions use digits 1–5 without repetition. How many strings are possible?
For a two-digit even number from 1–5 without repetition, how many choices remain for the tens position after an even units digit is chosen?
When can counts for two cases be added directly?
Practice Problems
- Count three-digit numbers from 1–5 with repetition allowed and with repetition forbidden. Explain the changing choices.
- Count three-digit even numbers from 1–6 with repetition allowed.
- Count four-letter codes from ten different letters without repetition.
- Count five-digit identifiers that begin with 67 and use digits 0–9 without repetition.
- List the possible outcomes of three coin tosses and compare your list with the multiplication principle.
- Count ordered two-flag signals from five different flags.
- Explain why 2-flag and 3-flag signals are separate cases, while “signals containing red” and “signals containing blue” may overlap.
Key Takeaways
• Describe one complete outcome before counting. • Multiply stage counts when each path has the stated number of choices. • Repetition determines whether choices stay available. • A restricted position can be counted first. • Add separate cases only after checking overlap and completeness.
Previous
Start of chapter
Next · Lesson 2
Permutations of Distinct Objects