HN5 - Counting with the product rule

HN5 - Counting with the product rule

Count large sets of choices without writing every outcome. You will connect multiplication to systematic lists, adjust counts for restrictions, and check whether a calculation counts ordered arrangements or unordered selections.

Independent choices

How many codes have one letter from A, B, C or D followed by two digits from 00 to 99, if a digit may be repeated? There are too many to list comfortably, but the structure of a list gives a shortcut.

Recall a table with two cap colours and three sizes: each colour has three continuations. That makes 3+3=63+3=6 choices. Multiplication records the equal-sized groups: 2×3=62\times3=6.

Independent choices

For counting, choices are independent when an earlier choice does not restrict the options available at a later stage. If every cap colour comes in every size, the colour and size can be chosen independently.

With more stages, each complete outcome at one stage branches into all the options at the next. Each route through those stages represents a different complete outcome.

Product rule for counting

If there are mm first choices, and exactly nn continuations for each first choice, then

number of complete outcomes=m×n.\text{number of complete outcomes}=m\times n.

For another stage with exactly pp choices after every permitted earlier outcome, multiply again to get m×n×pm\times n\times p.

Not in the formula booklet: learn it.

The factors count the available options at each stage, not the number of stages. Codes can begin with zero in a digit position when the question permits it; they are labels rather than numbers with a specified number of digits.

Worked example 1: a letter and a digit

Question. A code consists of one letter from A, B, C or D, followed by one digit from 00 to 99. How many codes are possible?

Plan. Count the letter options and the digit options, then multiply.

letter choices=4digit choices after each letter=10codes=4×10=40\begin{aligned} \text{letter choices}&=4\\ \text{digit choices after each letter}&=10\\ \text{codes}&=4\times10=40 \end{aligned}

For example, A can be followed by any of the ten digits. Exactly the same ten options follow B, C and D.

Answer. 4040 codes.

Check. Group by the final digit instead. Each of the ten digits can follow any of four letters, giving 10×4=4010\times4=40.

Add one digit position. Repetition is still allowed, so using a digit does not reduce the next choice set.

Worked example 2: adding a stage

Question. A code consists of one letter from A, B, C or D, followed by two digits from 00 to 99. Digits may be repeated. How many codes are possible?

Plan. Extend each letter-and-digit code with all ten possible final digits.

letter choices=4first digit choices=10second digit choices=10codes=4×10×10=400\begin{aligned} \text{letter choices}&=4\\ \text{first digit choices}&=10\\ \text{second digit choices}&=10\\ \text{codes}&=4\times10\times10=400 \end{aligned}

The repeated-digit code A77 is allowed, as is A00. Swapping unequal digits changes their positions, so A27 and A72 are different codes.

Answer. 400400 codes.

Check. After each letter, the two-digit strings run from 00 through 99: one hundred strings, including those starting with zero. Four groups of one hundred give 400400.

Adding the choices would count isolated letters and digits, rather than combine them into complete codes.

Watch out

4+10+10=244+10+10=24 does not count three-character codes. Choose a letter and then a digit and then another digit: the choices combine by multiplication.

Use the same structure with a new set of letters.

Restricted choices

When a choice uses up an option or excludes some possibilities, count what is actually available at the next stage.

You can still multiply when the number of continuations is the same after every permitted earlier choice. The identities of those continuations may differ. For instance, choosing one digit without replacement leaves nine other digits, whichever digit was chosen.

Worked example 3: no repeated digits

Question. A four-digit lock code uses digits from 00 to 99. No digit may be repeated, and the code may start with zero. How many codes are possible?

Plan. Reduce the available digit count by one after each position is filled.

position1234choices10987\begin{array}{c|cccc} \text{position}&1&2&3&4\\\hline \text{choices}&10&9&8&7 \end{array}

After the first digit there are nine unused digits. After the second there are eight, then seven after the third.

10×9×8×7=504010\times9\times8\times7=5040

Answer. 50405040 codes.

Check. Fix the last digit instead. There are ten options for it, then nine, eight and seven for the other positions: the same 50405040 distinct codes.

Now change only the meaning of the result: it must be a four-digit number. A leading zero is no longer allowed.

Worked example 4: excluding a leading zero

Question. How many four-digit numbers use digits from 00 to 99 without repetition?

Plan. Exclude zero from the first position, then count the unused digits.

position1234choices9987\begin{array}{c|cccc} \text{position}&1&2&3&4\\\hline \text{choices}&9&9&8&7 \end{array}

There are nine non-zero first digits. There are still nine second digits: zero is now allowed, while the chosen first digit is unavailable.

9×9×8×7=45369\times9\times8\times7=4536

Answer. 45364536 four-digit numbers.

Check. From the previous example, remove the codes starting with zero. These have 9×8×7=5049\times8\times7=504 continuations, so 5040−504=45365040-504=4536.

More detailed restrictions work the same way. Fill positions in an order that lets you count their options clearly, and ensure earlier choices have not used any options you need later.

Worked example 5: comparing restricted and unrestricted codes

Question. Six cards show 1, 2, 3, 4, 6, 81,\ 2,\ 3,\ 4,\ 6,\ 8. Each card must be used exactly once in a six-digit code. A restricted code must have an even first digit and odd second and third digits. How many more unrestricted codes are there than restricted codes?

Plan. Find each count separately, then subtract the restricted count.

With no restrictions, each position uses one card:

unrestricted codes=6×5×4×3×2×1=720.\text{unrestricted codes}=6\times5\times4\times3\times2\times1=720.

For restricted codes, the first digit is one of 2, 4, 6, 82,\ 4,\ 6,\ 8, giving four choices. The odd digits are 11 and 33, so the second position has two choices and the third has one. Three unused cards remain for the last three positions.

restricted codes=4×2×1×3×2×1=48difference=720−48=672\begin{aligned} \text{restricted codes}&=4\times2\times1\times3\times2\times1=48\\ \text{difference}&=720-48=672 \end{aligned}

The first choice cannot remove an odd digit, because it must be even. That is why the second-position count is always two.

Answer. 672672 more unrestricted codes.

Check. Fix one allowed first digit. The odd pair can be 1313 or 3131. For either pair, the last three cards have the six orders obtained by listing their first card and swapping the other two. That gives 2×6=122\times6=12 codes for each of four first digits: 4848. The excluded 672672 and allowed 4848 add back to 720720.

Restrictions must be applied to their stated positions, rather than subtracting a fixed amount from every factor.

Watch out

For four-digit numbers without repetition, 9×8×7×69\times8\times7\times6 wrongly excludes zero from every position. Only the first position forbids zero; the correct factors are 9,9,8,79,9,8,7.

Try a different set of six cards with the same position restrictions.

Checking a count

A short list or a small tree can reveal what a product counts and whether it includes forbidden or repeated outcomes.

First check that the branch sizes match the factors. Suppose a code starts with A, B or C. After A or C the digit can be 11 or 22, but after B it must be 11. The complete list is A1, A2, B1, C1, C2. The count is

2+1+2=5,2+1+2=5,

not 3×2=63\times2=6, which would include the forbidden B2. When different branches have different numbers of continuations, count those separate cases and add them.

Also check what swapping two choices does. A product for “first person, then second person” counts ordered choices. Different roles make those distinct, but equal roles may make them the same selection.

[DIAGRAM: asset_name: Ordered roles and unordered teams; asset_slug: ordered-pair-grid; caption: Each pair of reflected cells gives two role assignments but one team.; description: A five by five grid labels both axes E, F, G, H and J. The diagonal is excluded because a person cannot be selected twice. Ten blue cells above the diagonal and ten rose cells below contain reversed pairs such as EF and FE. A note shows that these are two captain-and-deputy assignments but one two-person team.]
Each pair of reflected cells gives two role assignments but one team.

Worked example 6: ordered roles

Question. Eli, Fatima, Gus, Hana and Jo can be captain or deputy. One person cannot hold both roles. How many captain-and-deputy assignments are possible?

Plan. Choose the captain, then choose a different person as deputy.

captain choices=5deputy choices for each captain=4assignments=5×4=20\begin{aligned} \text{captain choices}&=5\\ \text{deputy choices for each captain}&=4\\ \text{assignments}&=5\times4=20 \end{aligned}

Eli as captain with Fatima as deputy differs from Fatima as captain with Eli as deputy, so both must count.

Answer. 2020 assignments.

Check. A tree has five first-stage branches and four ends after each. The grid shows the same twenty choices: its five diagonal cells are forbidden and its other twenty cells are allowed.

Keep the same five people but change the roles to equal places on a team.

Worked example 7: unordered teams

Question. Two people from Eli, Fatima, Gus, Hana and Jo form a team with equal roles. How many teams are possible?

Plan. Begin with the ordered count and identify how many times each team appears.

The product 5×4=205\times4=20 includes each team twice: for example, EF and FE. Every team has two different members, so every team has exactly these two orders.

teams=5×42=10\text{teams}=\frac{5\times4}{2}=10

Answer. 1010 teams.

Check. List each team with the alphabetically earlier initial first:

EF, EG, EH, EJ;FG, FH, FJ;GH, GJ;HJ.\mathrm{EF},\ \mathrm{EG},\ \mathrm{EH},\ \mathrm{EJ};\quad \mathrm{FG},\ \mathrm{FH},\ \mathrm{FJ};\quad \mathrm{GH},\ \mathrm{GJ};\quad \mathrm{HJ}.

The groups contain 4+3+2+1=104+3+2+1=10 teams, matching the ten blue cells in the grid.

The division by two is justified by the pair of orders for each team. If repeated choices were allowed, a pair such as EE would have only one order, so the same division would need reconsidering.

Key idea

Check two things: every factor matches the permitted continuations, and each complete object is counted exactly once.

For the opening code question, the digit positions are different and repetition is allowed. There are 4×10×10=4004\times10\times10=400 codes; A27 and A72 must both count, so no division by two is needed.

Quick Recap

  • Multiply stage counts when every permitted earlier outcome has the stated number of continuations.
  • Adjust the factors for restrictions, including repetition and leading zeros.
  • Add counts for separate cases when their branch sizes differ.
  • An unordered pair of different objects has two orders; justify any division that removes repeated counting.

The opening letter-and-two-digit code has 400400 possibilities.