Chapter 25 — Learning to Count
Table of Contents
25.1 Counting with Multiplication
The Multiplication Principle. If task 1 can be done in $m$ ways and task 2 can be done in $n$ ways (independently), then both tasks together can be done in $m \times n$ ways.
More generally, if there are $k$ tasks that can be done in $n_1, n_2, \ldots, n_k$ ways respectively, the total number of ways is $n_1 \cdot n_2 \cdots n_k$.
Example 25-1. A restaurant offers 3 appetizers, 5 entrees, and 2 desserts. How many different 3-course meals are possible?
\(3 \times 5 \times 2 = 30.\)
Example 25-2 (Counting Divisors). How many positive divisors does $n = 2^3 \cdot 3^2 \cdot 5^1$ have?
A divisor has the form $2^a \cdot 3^b \cdot 5^c$ where $0 \leq a \leq 3$, $0 \leq b \leq 2$, $0 \leq c \leq 1$.
Choices: $4 \times 3 \times 2 = 24$ divisors.
Restricted Counting. When there are restrictions, handle the most-restricted positions first.
Example: How many 4-digit numbers have no repeated digits? The first digit has 9 choices (can’t be $0$), the second has 9 (any digit except the first), the third has 8, the fourth has 7: $9 \times 9 \times 8 \times 7 = 4536$.
Exercise 25-1. How many license plates can be formed with 3 letters followed by 3 digits?
Exercise 25-2. How many positive divisors does $10! = 2^8 \cdot 3^4 \cdot 5^2 \cdot 7$ have?
Exercise 25-3. How many 3-digit numbers have all digits odd?
25.2 Permutations
Factorial. $n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$. By convention, $0! = 1$.
Permutation. An arrangement of $n$ distinct objects in a specific order. The number of permutations of $n$ objects is $n!$.
The number of permutations of $n$ objects taken $r$ at a time:
\(P(n,r) = \frac{n!}{(n-r)!}\)
Example 25-3. How many ways can 8 people line up?
\(8! = 40320.\)
Example 25-4. How many ways can 3 people be chosen from 8 to sit in a row (order matters)?
\(P(8,3) = \frac{8!}{5!} = 8 \times 7 \times 6 = 336.\)
Circular Permutations
The number of ways to arrange $n$ distinct objects in a circle is:
\[(n-1)!\](We fix one object and arrange the remaining $n-1$.)
For a keychain (or necklace), where rotations and reflections are the same:
\(\frac{(n-1)!}{2}\)
Exercise 25-4. How many ways can 6 people sit around a circular table?
Exercise 25-5. How many distinct necklaces can be made from 6 different beads?
25.3 Combinations
Definition. A combination is a selection where order doesn’t matter. The number of ways to choose $k$ objects from $n$ is:
\[\binom{n}{k} = C(n,k) = \frac{n!}{k!(n-k)!}\]Read “$n$ choose $k$.”
Example 25-5. From 8 people, how many ways can a committee of 3 be chosen?
\(\binom{8}{3} = \frac{8!}{3! \cdot 5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56.\)
Permutation vs. Combination. If order matters, use $P(n,r)$. If order doesn’t matter, use $\binom{n}{r}$.
Connection: $P(n,r) = \binom{n}{r} \cdot r!$ — first choose, then arrange.
Overcounting / Division Principle. When we count arrangements but some are “the same,” divide by the number of repetitions.
Example: How many ways to choose a president, VP, and secretary from 10 people? That’s $P(10,3) = 720$. But if we just want a 3-person committee (no roles): $720 / 3! = 120 = \binom{10}{3}$.
Exercise 25-6. How many diagonals does a convex decagon (10-gon) have?
Exercise 25-7. From 5 math books and 3 history books, how many ways can you choose 2 math and 1 history?
25.4 Distinguishability
Key Question. Are the objects we’re arranging distinguishable (individually identifiable) or indistinguishable (identical)?
Example 25-6 (Multinomial Arrangements). How many distinct arrangements of the letters in MISSISSIPPI?
There are 11 letters: M(1), I(4), S(4), P(2).
\(\frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = \frac{39916800}{1 \cdot 24 \cdot 24 \cdot 2} = 34650.\)
Multinomial Coefficient. The number of ways to arrange $n$ objects where there are $n_1$ of type 1, $n_2$ of type 2, …, $n_k$ of type $k$ (with $n_1 + n_2 + \cdots + n_k = n$):
\(\frac{n!}{n_1!\, n_2!\, \cdots\, n_k!}\)
Stars and Bars. To distribute $n$ identical objects into $k$ distinct bins:
\[\binom{n + k - 1}{k - 1}\]Think of $n$ stars and $k-1$ bars (dividers). The total number of symbols is $n + k - 1$, and we choose where to place the $k - 1$ bars.
Exercise 25-8. How many distinct arrangements of the letters in BANANA?
Exercise 25-9. How many ways can 10 identical candies be distributed among 4 children?
25.5 Casework and Complementary Counting
Casework
Casework (Addition Principle). If a problem can be split into mutually exclusive cases, count each case separately and add.
Example. How many 3-digit even numbers have digit sum $\leq 5$?
Case 1: last digit $= 0$. Need first two digits with sum $\leq 5$, first digit $\geq 1$. Enumerate: $(1,0), (1,1), (1,2), (1,3), (1,4), (2,0), (2,1), (2,2), (2,3), (3,0), (3,1), (3,2), (4,0), (4,1), (5,0)$ → 15 numbers.
Case 2: last digit $= 2$. Need first two digits with sum $\leq 3$, first $\geq 1$: $(1,0), (1,1), (1,2), (2,0), (2,1), (3,0)$ → 6 numbers.
Case 4: last digit $= 4$. Sum $\leq 1$, first $\geq 1$: $(1,0)$ → 1 number.
Total: $15 + 6 + 1 = 22$.
Complementary Counting
Complementary Counting. Instead of counting what you want, count what you don’t want and subtract:
\(\text{Desired} = \text{Total} - \text{Undesired}\)
Example. How many 4-digit numbers have at least one repeated digit?
Total 4-digit numbers: $9000$ (from $1000$ to $9999$).
No repeated digits: $9 \times 9 \times 8 \times 7 = 4536$.
At least one repeat: $9000 - 4536 = 4464$.
Exercise 25-10. How many integers from 1 to 1000 are not divisible by 3, 5, or 7? (Use inclusion-exclusion.)
25.6 The Binomial Theorem
The Binomial Theorem. For any non-negative integer $n$:
\((x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k = \binom{n}{0}x^n + \binom{n}{1}x^{n-1}y + \cdots + \binom{n}{n}y^n\)
Example 25-7. Expand $(x + y)^4$:
\[(x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4.\]Coefficients: $1, 4, 6, 4, 1$ — the 4th row of Pascal’s Triangle.
Pascal’s Triangle
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Pascal’s Identity:
\[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\]Each entry is the sum of the two entries above it.
Useful Identities.
Setting $x = y = 1$: $\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n$ (total number of subsets of an $n$-element set).
Setting $x = 1, y = -1$: $\displaystyle\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$ (even-sized subsets = odd-sized subsets).
Exercise 25-11. What is the coefficient of $x^5 y^3$ in $(x + y)^8$?
Exercise 25-12. Expand $(2a - b)^4$ using the Binomial Theorem.
Problems to Solve for Chapter 25
Problem 457. A “word” is any sequence (even meaningless) of letters. How many 5-letter words have no repeated letters? (MATHCOUNTS 1991)
Problem 458. A dinner party has 8 guests seated around a circular table. How many different seating arrangements are possible? (AHSME 1964)
Problem 459. How many 4-letter words can be made from the letters A, B, C, D, E if repetition is allowed? (MAΘ 1990)
Problem 460. How many committees of 5 can be formed from 6 men and 4 women if the committee must include at least 1 woman? (AHSME 1968)
Problem 461. In how many ways can 7 people be divided into a group of 4 and a group of 3?
Problem 462. A set of $n$ objects can be split into two groups. Each group must have at least one object. In how many ways can this be done if the groups are unordered?
Problem 463. How many distinct arrangements of the letters in TOOT are there?
Problem 464. How many paths from $A$ to $B$ go only right or down on a 4 × 3 grid? (Classic lattice path problem)
Problem 465. In the expansion of $(x + y)^{10}$, what is the sum of the coefficients?
Problem 466. How many diagonals does a convex 20-gon have? (MATHCOUNTS 1989)
Problem 467. Six friends go to a movie theater and sit in a row. How many arrangements are there if two particular friends refuse to sit next to each other?
Problem 468. Find the coefficient of $a^3 b^4$ in $(a + b)^7$.
Problem 469. A pizza place offers 10 toppings. How many different pizzas can you order (each topping is either on or off)?
Problem 470. How many triangles can be formed by connecting vertices of a regular 12-gon?
Problem 471. How many 5-digit palindromes are there? (A palindrome reads the same forwards and backwards.)
Problem 472. A coin is flipped 10 times. In how many ways can you get exactly 6 heads?
Problem 473. How many nonnegative integer solutions are there to $x + y + z = 10$?
Problem 474. In the expansion of $(2x - 3)^5$, find the coefficient of $x^3$.
Problem 475. Seven books are on a shelf: 3 math and 4 science. If the math books must stay together, how many arrangements are there?
Problem 476. Show that $\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n$ using the Binomial Theorem.
Problem 477. Prove Pascal’s Identity: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$.