Section 1.2: Methods of Enumeration
Master counting techniques: multiplication principle, permutations, combinations, and multinomial coefficients.
The Multiplication Principle
If an experiment has two parts where the first part has m outcomes and the second part has n outcomes, then the total number of outcomes is m × n.
Example: License Plates
A license plate has 3 letters followed by 4 digits. How many unique plates are possible?
Permutations
A permutation is an ordered arrangement. When order matters, we use permutations.
Factorial: n!
The number of ways to arrange all n distinct objects.
Note: 0! = 1 by definition
P(n,r) or ₙPᵣ
The number of ways to select r objects from n where order matters.
= n × (n-1) × ... × (n-r+1)
When to Use Permutations
- • Arranging people in a line or seats
- • Awarding 1st, 2nd, 3rd place (rankings)
- • Creating passwords/codes where order matters
- • Any scenario where ABC ≠ BAC ≠ CAB
Combinations
A combination is a selection where order does not matter. Also called "n choose r" or binomial coefficient.
Formula: C(n,r) or (n choose r)
Key Properties
- • C(n,r) = C(n, n-r) — symmetry
- • C(n,0) = C(n,n) = 1
- • C(n,1) = n
- • Sum of row n = 2ⁿ
When to Use Combinations
- • Selecting a committee (no positions)
- • Choosing cards in poker/bridge hands
- • Picking lottery numbers
- • Any scenario where {A,B,C} = {C,A,B}
Sampling: With vs Without Replacement
| Scenario | Ordered | Unordered |
|---|---|---|
| With Replacement | nʳ | C(n+r-1, r) |
| Without Replacement | P(n,r) = n!/(n-r)! | C(n,r) = n!/[r!(n-r)!] |
Exam Tip
Always ask yourself two questions: (1) Does order matter? (2) Can items be reused? This determines which formula to use.
Distinguishable Permutations & Multinomial Coefficients
When arranging n objects where some are identical, we divide by the factorials of the group sizes.
Multinomial Coefficient
Example: MISSISSIPPI
How many ways to arrange the letters in "MISSISSIPPI"?
11 letters: M(1), I(4), S(4), P(2)
11! / (1! × 4! × 4! × 2!) = 34,650 arrangements