STEP-BY-STEP LESSON · §9.2
Possibility Trees and the Multiplication Rule
Count successive choices using the multiplication rule.
Before you begin
Multiplication
A product m·n combines m equal groups of n objects when m,n are nonnegative integers. In counting, explain what the groups represent before multiplying; unequal branches must be counted separately.
Symbols
- m·n
- number of pairs with m and n choices
- n,r
- Integer population size n≥0 and chosen length 0≤r≤n
Definitions and notation for this topic
Factorial
n!
For integer n≥1, the product of the integers from 1 through n; by definition 0!=1.
There are 24 ways to order four distinct objects.
Separate glossary example
4! = 1×2×3×4 = 24
Permutations: number of ordered selections
P(n,k)=n!/(n−k)!
For integers n≥0 and 0≤k≤n, P(n,k) counts ordered selections of k distinct objects from n distinct objects, without repetition.
P(n,k) is the number of choices, not one choice itself. At k=n this becomes n!; at k=0 there is one empty selection.
Separate glossary example
P(5,2)=5·4=20 ordered pairs; choosing A then B differs from B then A.
P(4,2)=4×3=12
Product rule
For successive choices, multiply the numbers of options when each earlier choice has the same number of continuations.
Tutor example: every shirt can be paired with either pair of trousers.
Separate glossary example
3 shirts × 2 pairs of trousers = 6 outfits.
Step by step
Step 1 / 6
Split the choice into stages
For example, choose a letter, then a digit. One result is a complete pair.
Stages help avoid missing possibilities.
Worked example
A code contains one letter A,B,C followed by one digit 1,2. How many codes?
- The first stage chooses the letter; the second stage chooses the digit. Order is fixed in the code.
- For A there are A1,A2; for B, B1,B2; for C, C1,C2.
- Three branches with two outcomes each: 3·2=6.
Optional self-check
A permits two suffixes and B permits four. Why is the total 6, not 2·4?
Show answer
A and B are alternative disjoint branches, so add 2+4. No result chooses both an A suffix and a B suffix.