Chapter 2: Counting
To compute a probability, you need the skill of counting "how many ways" something can happen. In this chapter, we learn how to count the number of cases accurately.
2.1 The Product Rule
The basic idea
When you make two choices in sequence, the total number of cases is found by multiplication.
Example: outfit combinations
If you have 3 shirts and 2 pairs of pants, how many combinations are there?
The Product Rule (Multiplication Principle)
If choice A can be made in $m$ ways and choice B in $n$ ways, then doing A and then B can be done in $m \times n$ ways.
Three or more choices
The same holds for three or more choices.
Example: three-digit numbers
If each digit can be any of 1 to 9 (0 is not used), how many three-digit numbers are there?
$$9 \times 9 \times 9 = 729 \text{ ways}$$2.2 The Sum Rule
The basic idea
When you combine cases that do not overlap, the total number of cases is found by addition.
Example: choosing a dessert
For dessert there are 3 kinds of cake and 2 kinds of ice cream. If you pick just one of them, how many choices are there?
The Sum Rule (Addition Principle)
If case A can occur in $m$ ways and case B in $n$ ways, and A and B do not overlap, then the number of ways for A or B is $m + n$.
“Do not overlap” means nothing belongs to both groups at once. For instance, no dessert is a cake and an ice cream at the same time, so we can count them as $3 + 2$ with no double-counting. If the groups did overlap, we would have to subtract the overlap.
When you are unsure which to use
- “Do A and then also do B” (A and B) → multiply — the product rule.
- “Choose either A or B” (no overlap) → add — the sum rule.
2.3 Permutations (arrangements)
What is a permutation?
The number of ways to arrange distinct objects in order is called a permutation.
Example: arranging 3 people in a row
In how many ways can three people, A, B, and C, be arranged in a row?
Factorials
The number of ways to arrange all $n$ objects is written $n!$ (read as "$n$ factorial").
$$n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$$| $n$ | $n!$ | Computation |
|---|---|---|
| 0 | 1 | (special convention) |
| 1 | 1 | 1 |
| 2 | 2 | 2 × 1 |
| 3 | 6 | 3 × 2 × 1 |
| 4 | 24 | 4 × 3 × 2 × 1 |
| 5 | 120 | 5 × 4 × 3 × 2 × 1 |
Permutations of only some of the objects
The number of ways to choose $r$ objects from $n$ and arrange them is written $_nP_r$.
$$_nP_r = n \times (n-1) \times \cdots \times (n-r+1) = \dfrac{n!}{(n-r)!}$$Example: choosing and arranging 3 of 5 people
$$_5P_3 = 5 \times 4 \times 3 = 60 \text{ ways}$$2.4 Combinations (selections)
What is a combination?
The number of ways to choose some objects from distinct ones, without regard to order, is called a combination.
Example: choosing 3 of 5 people
Choose 3 of the 5 people A, B, C, D, and E.
In permutations, ABC and ACB counted as different, but as a combination they are the same selection: "A, B, and C were chosen."
The combination formula
The number of ways to choose $r$ objects from $n$ is written $_nC_r$ or $\binom{n}{r}$.
$$_nC_r = \dfrac{_nP_r}{r!} = \dfrac{n!}{r!(n-r)!}$$Example: choosing 3 of 5 people
$$_5C_3 = \dfrac{5!}{3! \times 2!} = \dfrac{120}{6 \times 2} = 10 \text{ ways}$$Why divide by $r!$?
In the permutation count $_5P_3 = 60$, each choice of the same 3 people has been counted $3! = 6$ times.
Example: the selection {A, B, C} is counted as the 6 arrangements ABC, ACB, BAC, BCA, CAB, CBA.
So $60 \div 6 = 10$ ways.
A property of combinations
$$_nC_r = {}_nC_{n-r}$$Choosing $r$ objects from $n$ is the same as deciding which $n-r$ objects to leave out.
Example: $_5C_3 = {}_5C_2 = 10$
2.5 Key Formulas and Computational Techniques
Pascal's triangle
$$_nC_r = {}_{n-1}C_{r-1} + {}_{n-1}C_r$$The meaning of this identity is clear from the figure: in Pascal's triangle, each number is the sum of the two numbers immediately above it to the left and right.
Commonly used values
| $_nC_r$ | r=0 | r=1 | r=2 | r=3 | r=4 | r=5 |
|---|---|---|---|---|---|---|
| n=5 | 1 | 5 | 10 | 10 | 5 | 1 |
| n=6 | 1 | 6 | 15 | 20 | 15 | 6 |
| n=7 | 1 | 7 | 21 | 35 | 35 | 21 |
2.6 Chapter Summary
| Rule / Formula | Meaning | Expression |
|---|---|---|
| Product rule | Consecutive choices multiply | $m \times n$ |
| Sum rule | Non-overlapping cases add | $m + n$ |
| Permutation $_nP_r$ | Number of arrangements | $\dfrac{n!}{(n-r)!}$ |
| Combination $_nC_r$ | Number of selections | $\dfrac{n!}{r!(n-r)!}$ |
Relationship between permutations and combinations: $_nC_r = \dfrac{_nP_r}{r!}$
Exercises
Problem 1
In how many ways can 4 people be arranged in a row?
Problem 2
In how many ways can a chairperson and a vice-chairperson be chosen from 10 people?
Problem 3
In how many ways can 2 committee members be chosen from 10 people?
Problem 4
In how many ways can 3 letters be chosen and arranged from the 5 letters A, B, C, D, E?
Solution
Solution to Problem 1
$4! = 24$ ways (arranging 4 people in a row = a permutation)
Solution to Problem 2
$_{10}P_2 = 10 \times 9 = 90$ ways (the chairperson and vice-chairperson are distinguished).
Solution to Problem 3
$_{10}C_2 = \dfrac{10 \times 9}{2} = 45$ ways (the committee members are not distinguished).
Solution to Problem 4
$_5P_3 = 5 \times 4 \times 3 = 60$ ways (arranging 3 people in order = a permutation)
Frequently Asked Questions
How do you decide between the product rule and the sum rule?
For choices made in sequence (do A and then also do B), use multiplication — the product rule. For picking just one of two options (A or B, with no overlap), use addition — the sum rule. A handy guide: “A and B” means product, “A or B” means sum.
What is the difference between permutations and combinations?
A permutation $P(n,r)$ is the number of ways to arrange $r$ objects with the order taken into account, while a combination $C(n,r)$ is the number of ways to choose $r$ objects with the order ignored. The same selection is counted differently depending on whether you count its ordering, and they are related by $C(n,r) = P(n,r)/r!$.
What is a factorial n!?
$n!$ is the product of all the integers from $1$ to $n$, and it gives the total number of permutations of $n$ objects arranged in a row. For example, $3! = 3 \times 2 \times 1 = 6$. By convention, $0!$ is defined to be $1$.