Difficulty: Introductory to Intermediate | Prerequisites: Sample spaces and events (Chapter 2, Part 1). Comfortable with factorial notation (n!).
Once you can describe a sample space, the next question is: how large is it? Counting techniques let you calculate the size of a sample space (or an event) without listing every outcome. This matters because probability often reduces to a fraction where the numerator and denominator are both counts. The multiplication rule, permutations, and combinations are the three core tools, and nearly every counting problem in this course uses one or a combination of them. Master these and the probability chapters that follow become far more mechanical.
The multiplication rule counts multi-step outcomes by multiplying the number of choices at each step. Permutations count ordered arrangements; combinations count unordered selections. When identical items repeat, use the multinomial coefficient to avoid overcounting.
Multiplication rule (fundamental counting principle)
If an operation can be performed in n₁ ways, and for each of those a second operation can be performed in n₂ ways, then the two operations together can be performed in n₁ × n₂ ways. Extends to any number of steps.
Think of it as a decision tree: each branch at step 1 splits into branches at step 2, and you multiply the counts.
Factorial (n!)
The product of all positive integers from 1 to n. By convention, 0! = 1.
In simple terms, n! is the number of ways to arrange n distinct objects in a line.
Permutation (nPr)
The number of ordered arrangements of r objects chosen from n distinct objects: nPr = n! / (n − r)!.
Think of it as "pick r items from n, and the order you pick them in matters." First place, second place, third place in a race is a permutation problem.
Combination (nCr or "n choose r")
The number of ways to choose r objects from n distinct objects when order does not matter: nCr = n! / (r!(n − r)!).
In simple terms, you are forming a group, not a sequence. A committee of 3 chosen from 7 people is a combination problem.
Multinomial coefficient
The number of distinguishable permutations of n objects when there are groups of identical items. If there are n₁ of type 1, n₂ of type 2, ..., nₖ of type k (with n₁ + n₂ + ... + nₖ = n), the count is n! / (n₁! × n₂! × ... × nₖ!).
Think of it as correcting for overcounting. Swapping two identical oak trees does not create a new arrangement, so you divide out the redundant swaps.
Distinguishable permutations
Another name for the result of the multinomial coefficient. Used when arranging objects that include repeats (e.g. letters of a word with repeated letters, or trees of the same species).
The multiplication rule is the workhorse. Whenever an outcome is built in stages, multiply the number of options at each stage.
Q2.24: A student can be classified by class standing (4 options) and gender (2 options). Total classifications = 4 × 2 = 8.
Q2.28: A doctor can choose from 5 manufacturers, 3 preparations, and 2 strengths for an asthma drug. Total choices = 5 × 3 × 2 = 30.
Additional Problem 1: A 4-digit security code where the first digit is not zero (9 choices) and the last digit is odd (5 choices), with the middle two digits unrestricted (10 choices each). Total = 9 × 10 × 10 × 5 = 4,500.
Additional Problem 5: 8-letter usernames from 26 letters (case-insensitive), with repetition allowed. Total = 26⁸ ≈ 208.8 billion.
The rule extends naturally: for k steps with n₁, n₂, ..., nₖ options, the total is n₁ × n₂ × ... × nₖ.
Use permutations when you are filling distinct positions from a pool of distinct objects.
Q2.32(a): Arranging 6 people in a line. All 6 are used, so it is 6! = 720.
Q2.32(b): 3 specific people must stand together. Treat them as a single block (4! internal arrangements of the block × 3! arrangements of the remaining block-and-people unit, giving 4 × 3! × 3! = 24 × 6 = 144). More precisely: the block of 3 can be internally ordered in 3! = 6 ways, and the block plus the other 3 people form 4 units arranged in 4! = 24 ways, so 24 × 6 = 144.
Q2.32(c): 2 specific people refuse to stand next to each other. Count the complement: total arrangements (720) minus arrangements where they are adjacent. Treat the pair as a block: (5)(2!)(4!) = 240 ways they are adjacent. Answer: 720 − 240 = 480.
Q2.39(a): 8 finalists in a spelling bee, all positions matter. 8! = 40,320.
Q2.39(b): Only the first three positions matter. ₈P₃ = 8!/5! = 336.
Q2.42: Choosing 3 winners from 40 contestants. ₄₀P₃ = 40!/37! = 59,280.
Additional Problem 3: Top 3 finishers from 43 race cars. ₄₃P₃ = 43 × 42 × 41 = 74,046.
Use combinations when you are selecting a group with no ranking or sequence.
Q2.26(a): Choosing 5 items from 7. C(7,5) = 21.
Q2.26(b): Choosing 3 items from 5. C(5,3) = 10.
Additional Problem 4: Selecting 3 microwave ovens from a shipment of 10 (2 defective, 8 good).
(a) No defective: choose 3 from 8 good ones. C(8,3) = 56.
(b) Exactly 1 defective: choose 1 from 2 defective and 2 from 8 good. C(2,1) × C(8,2) = 2 × 28 = 56.
(c) At least 2 defective: choose 2 from 2 defective and 1 from 8 good. C(2,2) × C(8,1) = 1 × 8 = 8. Alternatively, total ways minus (no defective) minus (one defective) = C(10,3) − 56 − 56 = 120 − 112 = 8.
The complementary approach in part (c) is worth noting: sometimes it is easier to count what you do not want and subtract.
When digits or items have constraints, handle each constraint carefully.
Q2.36(a): 3-digit numbers from {1,2,3,4,5,6}, no repetition. Hundreds place: 6 choices. Tens: 6 remaining minus 1 = 5... wait, there are only 6 digits. 6 × 5 × 4... but the solution gives (6)(6)(5) = 180. This is because 0 is excluded from the set, and the problem uses digits {1,2,3,4,5,6} with the hundreds digit having 6 options, tens having 6 options (all 6 nonzero, but one used), leaving 5 for units. Per the solution: 6 × 6 × 5 = 180.
Q2.36(b): Odd 3-digit numbers. Units must be odd (3 choices: 1, 3, 5). Hundreds: 5 remaining nonzero digits. Tens: 5 remaining. Total = 3 × 5 × 5 = 75.
Q2.36(c): 3-digit numbers greater than 330. Split into cases by the hundreds digit. If hundreds digit is 4, 5, or 6: 3 × 6 × 5 = 90. If hundreds digit is 3: tens must be 4, 5, or 6 (to exceed 330), giving 1 × 3 × 5 = 15. Total = 90 + 15 = 105.
When arranging objects that include identical items, divide by the factorials of the group sizes to remove redundant orderings.
Q2.45: Arranging 8 objects with 3 of one kind and 2 of another. 8! / (3! × 2!) = 3,360.
Additional Problem 2: Planting 4 oak, 8 maple, and 6 poplar trees (18 total) in a row. 18! / (4! × 8! × 6!) = 9,189,180.
Multiplication rule:
\text{Total outcomes} = n_1 \times n_2 \times \cdots \times n_kPermutation (ordered selection of r from n):
{}_nP_r = \frac{n!}{(n-r)!}Combination (unordered selection of r from n):
\binom{n}{r} = \frac{n!}{r!\,(n-r)!}Multinomial coefficient (distinguishable permutations):
\frac{n!}{n_1!\, n_2!\, \cdots\, n_k!} \quad \text{where } n_1 + n_2 + \cdots + n_k = nRelationship between permutations and combinations:
{}_nP_r = \binom{n}{r} \times r!This makes sense: a permutation is a combination (choose the group) followed by an arrangement of that group (r! orderings).
Counting techniques show up whenever you need to compute probabilities by enumeration: the chance of a particular poker hand, the odds of winning a lottery, or the number of ways a quality inspector can sample items from a production batch. PIN codes, passwords, and license plates are all multiplication-rule problems at heart.
Using permutations when the problem calls for combinations (or vice versa). The single most common error. Ask yourself: does the order of selection matter? If you are choosing a committee, order does not matter (combination). If you are assigning ranked prizes, it does (permutation).
Forgetting to account for restrictions before multiplying. When a digit cannot be zero, or a position must be odd, handle the restricted positions first to avoid over- or under-counting.
Treating "at least" problems as a single calculation. "At least 2 defective" is easier to compute as total minus (0 defective) minus (1 defective), rather than trying to enumerate all qualifying cases directly.
Confusing "with repetition" and "without repetition." The 8-letter username problem (26⁸) allows repeated letters. If repetition were not allowed, it would be ₂₆P₈ = 26!/18!, a much smaller number.
⚠️ The most frequently tested skill is deciding whether a problem requires a permutation or a combination. Expect the exam to phrase problems ambiguously on purpose. Look for cues: "arrange," "line up," "first/second/third" signals permutation; "choose," "select," "committee," "group" signals combination.
⚠️ Problems with restrictions (digits that cannot repeat, positions that must be odd, items that must or must not be adjacent) appear regularly. Handle constrained positions first.
⚠️ Multi-part combination problems (like the defective-microwave question) test whether you can correctly apply the multiplication principle across categories: choose from defective AND from non-defective.
⚠️ Know the multinomial coefficient formula cold. It appears in questions about arranging letters of a word or objects with repeated types.
True or false: ₁₀P₃ is larger than C(10,3).
Fill in the blank: n! / (n − r)! gives the number of ______ arrangements of r objects from n.
True or false: C(n, 0) = 1 for any non-negative integer n.
How many ways can you arrange the letters of the word MISSISSIPPI? (Answer uses the multinomial coefficient.)
True or false: If repetition is allowed, choosing r items from n gives nʳ possibilities.
Answers: 1. True (₁₀P₃ = 720, C(10,3) = 120, because permutations count each ordering separately). 2. Ordered (permutation). 3. True (there is exactly one way to choose nothing). 4. 11! / (1! × 4! × 4! × 2!) = 34,650. 5. True.
Q: A PIN is 4 digits long. The first digit cannot be 0 and the last must be odd. How many PINs are possible?
A: First digit: 9 choices (1 through 9). Middle two digits: 10 choices each. Last digit: 5 choices (1, 3, 5, 7, 9). Total = 9 × 10 × 10 × 5 = 4,500.
Q: In how many ways can 43 race cars finish first, second, and third?
A: This is ₄₃P₃ = 43 × 42 × 41 = 74,046. Order matters because the positions are distinct.
Q: A landscaper plants 4 oaks, 8 maples, and 6 poplars in a row. How many distinguishable arrangements are there?
A: 18! / (4! × 8! × 6!) = 9,189,180. You divide by each group's factorial because swapping identical trees within a group does not produce a new arrangement.
Q: From a shipment of 10 ovens (2 defective, 8 good), a buyer picks 3. How many selections include exactly one defective oven?
A: Choose 1 defective from 2 and 2 good from 8: C(2,1) × C(8,2) = 2 × 28 = 56.
Q: Six people line up. How many arrangements exist if two specific people refuse to stand next to each other?
A: Total arrangements = 6! = 720. Arrangements where they are adjacent: treat the pair as one block, giving 5 units that can be ordered in 5! ways, and the pair can swap internally in 2! ways. Adjacent arrangements = 5! × 2! = 240. Answer = 720 − 240 = 480.
Q: How many 8-letter usernames can be formed from 26 letters (case-insensitive, repetition allowed)?
A: 26⁸. Each of the 8 positions has 26 independent choices.
Counting is the machinery behind discrete probability. When outcomes are equally likely, P(event) = (number of outcomes in the event) / (total outcomes in the sample space), and both numbers come from the techniques in this section.
The binomial coefficient C(n, r) reappears as the coefficient in the binomial probability distribution (Chapter 5). The multinomial coefficient generalises to the multinomial distribution. So the counting formulae here are not just exam material; they are structural components of later chapters.
Combinatorics also connects to the hypergeometric distribution, which models exactly the kind of "defective items in a sample" problem seen in Additional Problem 4.
Counting techniques, multiplication rule, fundamental counting principle, permutation, combination, n choose r, binomial coefficient, factorial, multinomial coefficient, distinguishable permutations, with repetition, without repetition, sampling with replacement, sampling without replacement, n factorial, nPr, nCr, complementary counting, restricted arrangements, adjacent constraint, STAT 3021, Walpole Ch. 2, combinatorics for probability