EN3 - Counting with the product rule

EN3 - Counting with the product rule

The product rule counts a large collection of outcomes by breaking each outcome into small choices. You will decide how many choices are available at each stage, handle simple restrictions and explain why arranging distinct objects leads to factorials. The crucial step is choosing the stages well.

Multiplying the choices at successive stages

Six different books sit on a shelf. If you tried a new order every minute, could you keep going for a full twelve hours without repeating one? Listing every order would take longer than finding the answer. We need to count routes without drawing every branch.

Begin with 22 shirts and 33 pairs of trousers. For each shirt, there are 33 outfits, giving 3+3=2×3=63+3=2\times3=6. Each outfit has exactly one shirt and one pair of trousers, so this construction neither misses an outfit nor counts it twice.

You already know

A complete route through a tree represents one complete outcome. Count the branches available after each earlier choice. A later stage may have fewer options if objects cannot be reused.

Instead of drawing the same set of branches repeatedly, multiply their numbers. Three stages with aa, bb and cc choices give aa groups, each containing bb groups of cc outcomes.

Product rule for counting

N=a1a2⋯akN=a_1a_2\cdots a_k

Use this when a complete outcome is built in kk stages and stage ii has aia_i choices after every allowed sequence of earlier choices. Each complete outcome must have exactly one construction.
Not on the formulae sheet: learn it.

The identities of the choices may depend on earlier stages. What must stay fixed for a single product is the number available at each stage. This is a counting rule; it does not require a probability calculation.

Worked example 1: choices from different categories

Question. A lunch consists of one of 44 sandwiches, one of 33 drinks and one of 22 fruits. Find the number of possible lunches.

Plan. Treat sandwich, drink and fruit as three successive choices.

sandwich and drink pairs=4×3=12three drinks per sandwichcomplete lunches=12×2=24two fruits per pair\begin{aligned} \text{sandwich and drink pairs}&=4\times3=12 && \text{three drinks per sandwich}\\ \text{complete lunches}&=12\times2=24 && \text{two fruits per pair} \end{aligned}

Why multiply? Every lunch needs one choice from every category. Adding 4+3+24+3+2 counts individual menu options, not complete lunches.

Answer. 2424 lunches.

Check. For each sandwich there are 3×2=63\times2=6 drink-and-fruit pairs, giving 6+6+6+6=246+6+6+6=24.

The next example changes one feature: the stages now repeat the same experiment, and the outcome records each stage separately.

Worked example 2: repeated stages

Question. Three six-sided dice are rolled in order. Find the number of possible ordered score sequences.

Plan. Count the six possible scores at each of the three positions.

first two scores=6×6=36all ordered pairsthree-score sequences=36×6=216six possible third scores\begin{aligned} \text{first two scores}&=6\times6=36 && \text{all ordered pairs}\\ \text{three-score sequences}&=36\times6=216 && \text{six possible third scores} \end{aligned}

Why keep the positions? (1,2,3)(1, 2, 3) and (3,2,1)(3, 2, 1) are different sequences, even though they contain the same three scores.

Answer. 216216 ordered score sequences.

Check. Fixing the first score leaves 3636 sequences; the six first-score cases give 6×36=2166\times36=216.

With nn six-sided dice recorded in order, the same argument gives 6n6^n sequences. This result is not on the formulae sheet: learn it. It counts sequences, not the number of possible totals.

Watch out

Wrong: 6+6+6=186+6+6=18 possible three-dice sequences. That adds the branch counts instead of extending every route. Right: 6×6×6=2166\times6\times6=216. Also, a count such as 216216 is not a probability: do not divide by a sample-space size unless asked for a probability.

Change the number of possible scores while keeping the number of stages fixed.

Choosing restricted positions first

A restriction changes a stage's available choices; handle the most restricted position before filling unrestricted ones.

For a four-digit PIN, 00 is allowed first, so 00470047 is a valid PIN. For a four-digit number, a leading 00 would produce a number with fewer than four digits. Words such as “number”, “code”, “distinct” and “without repetition” affect the factors you multiply.

Repetition allowed or forbidden

If repetition is allowed, a symbol used at one position can be used again. Without repetition, each chosen symbol is removed from later choices. For example, 272272 is allowed when repeated digits are permitted, but not when all digits must be distinct.

The product rule still works without repetition: although the remaining symbols change, their number may be the same on every route. From 55 distinct symbols, the second position always has 44 choices after filling the first.

Worked example 3: a restriction on the first position

Question. How many three-digit numbers can be formed from 0,1,2,3,40, 1, 2, 3, 4, if repetition is allowed?

Plan. Count non-zero choices for the hundreds digit, then all five choices at each other position.

hundreds choices=4zero is forbidden firsttens choices=5repetition is allowedunits choices=5repetition is allowedtotal=4×5×5=100complete numbers\begin{aligned} \text{hundreds choices}&=4 && \text{zero is forbidden first}\\ \text{tens choices}&=5 && \text{repetition is allowed}\\ \text{units choices}&=5 && \text{repetition is allowed}\\ \text{total}&=4\times5\times5=100 && \text{complete numbers} \end{aligned}

Why not 535^3? That would include strings starting with 00, which are not three-digit numbers.

Answer. 100100 three-digit numbers.

Check. There are 2525 numbers beginning with each of 1,2,3,41, 2, 3, 4, giving 100100 altogether.

The next example changes only whether repetition is permitted. The hundreds digit still cannot be 00.

Worked example 4: remove a used digit

Question. How many three-digit numbers can be formed from 0,1,2,3,40, 1, 2, 3, 4, if repetition is not allowed?

Plan. Fill the hundreds digit first, then reduce the number of remaining choices at each stage.

hundreds choices=4choose a non-zero digittens choices=4four digits remain, including zerounits choices=3two digits have been usedtotal=4×4×3=48product rule\begin{aligned} \text{hundreds choices}&=4 && \text{choose a non-zero digit}\\ \text{tens choices}&=4 && \text{four digits remain, including zero}\\ \text{units choices}&=3 && \text{two digits have been used}\\ \text{total}&=4\times4\times3=48 && \text{product rule} \end{aligned}

Why are the first two factors both 44? The first stage excludes 00. The second excludes the chosen hundreds digit but allows 00.

Answer. 4848 three-digit numbers.

Check. For each of the four possible hundreds digits, there are 4×3=124\times3=12 endings, giving 4848.

Sometimes no single product applies to every route. For an even three-digit number with distinct digits from 0,1,2,3,40, 1, 2, 3, 4, fill the units digit first. If it is 00, there are 4×3=124\times3=12 ways to fill the other positions. If it is 22 or 44, there are 3×3=93\times3=9 ways for each choice: the first digit cannot be 00 or the used even digit. These disjoint cases give 12+9+9=3012+9+9=30. Adding disjoint case totals is not on the formulae sheet: learn it.

Watch out

Wrong: count those even numbers as 3×4×3=363\times4\times3=36. After choosing a non-zero even units digit, there are only 33 legal hundreds digits. Right: separate “units digit 00” from “units digit 22 or 44”, then add the case totals.

The same zero restriction appears with a longer list of available digits.

Arranging all distinct objects and factorials

To arrange every object in a row, fill the positions one at a time; each occupied position leaves one fewer object for the next.

Three books labelled A,B,CA, B, C have the orders ABC,ACB,BAC,BCA,CAB,CBAABC, ACB, BAC, BCA, CAB, CBA. There are 33 choices first, 22 next and 11 last, giving 3×2×1=63\times2\times1=6. The same reasoning works for any finite number of distinct objects.

Factorial

For a positive integer nn, n!n!, read “nn factorial”, means the product of all positive integers from nn down to 11. For example, 4!=4×3×2×1=244!=4\times3\times2\times1=24. It is not 4×44\times4. Also define 0!=10!=1: there is one way to arrange no objects, namely the empty arrangement.

An arrangement here is linear: positions in a row are distinguished. The objects must be distinct, so swapping two changes the arrangement. A row of separately identifiable books fits this description; indistinguishable copies need different treatment.

Arranging all distinct objects

number of linear arrangements of n distinct objects=n!\text{number of linear arrangements of }n\text{ distinct objects}=n!

This holds for every non-negative integer nn, with 0!=10!=1.
Not on the formulae sheet: learn it.

There is no need to draw a tree with hundreds of endpoints. The decreasing stage counts already give its exact size.

Worked example 5: all positions are free

Question. Six different books are arranged in a row. Find the number of arrangements. Hence decide whether a different arrangement each minute can last for twelve hours.

Plan. Fill the six positions, then compare the count with the number of minutes available.

N=6×5×4×3×2×1one fewer choice each time=6!=720factorial notation12×60=720minutes in twelve hours\begin{aligned} N&=6\times5\times4\times3\times2\times1 && \text{one fewer choice each time}\\ &=6!=720 && \text{factorial notation}\\ 12\times60&=720 && \text{minutes in twelve hours} \end{aligned}

Why count books as distinct? Choosing a different title for any position changes the order on the shelf.

Answer. 720720 arrangements: exactly enough for 720720 consecutive one-minute slots, or twelve hours.

Check. Fixing the first book leaves 5!=1205!=120 orders. There are 66 possible first books, giving 6×120=7206\times120=720.

The next example changes one feature: a specified book has a fixed position.

Worked example 6: one object is fixed

Question. Six different books are arranged in a row. A specified dictionary must be at the left-hand end. Find the number of arrangements.

Plan. Fix the dictionary first, then arrange the five remaining books in the five remaining positions.

choices for the first position=1the dictionary is fixedarrangements of the rest=5!=120five distinct booksN=1×120=120combine the stages\begin{aligned} \text{choices for the first position}&=1 && \text{the dictionary is fixed}\\ \text{arrangements of the rest}&=5!=120 && \text{five distinct books}\\ N&=1\times120=120 && \text{combine the stages} \end{aligned}

Why not multiply by 66? The dictionary has one permitted position, not a choice of six positions.

Answer. 120120 arrangements.

Check. The 720720 unrestricted arrangements split into 66 equal groups according to which book is first. One group contains 720÷6=120720\div6=120.

Factorials grow fast: ten distinct books have 10!=3 628 80010!=3\,628\,800 orders. At one new order per second, that is exactly 4242 days. At that same speed, six books take only 720720 seconds, or 1212 minutes. Four extra books have increased the waiting time from minutes to weeks.

Watch out

Wrong: use 6!6! after fixing one of the six books at an end. That factorial still lets the fixed book move. Right: remove the fixed object and position, then use 5!5! for the rest.

Fixing a different shelf position has the same effect on the count.

Quick Recap

  • Break each complete outcome into stages and multiply the choices available at those stages.
  • Check leading zero, repetition and other restrictions before choosing the factors.
  • If the number of later choices depends on the case, count disjoint cases separately and add.
  • The number of linear arrangements of nn distinct objects is n!n!, with 0!=10!=1.

The opening shelf question: six distinct books give 6!=7206!=720 arrangements, exactly one for each minute of twelve hours.