High School Mathematics · Grades 10–12

27Combinatorics and Counting

Combinatorics is the art of counting without listing. Its two elementary principles — add the sizes of disjoint alternatives, multiply the numbers of independent choices — suffice to count the arrangements, permutations and subsets of a finite set, and culminate in the binomial theorem.

27.1 The two counting principles

We write $\abs{E}$ for the number of elements (the cardinality) of a finite set $E$ .

Proposition 27.1 (Addition principle)

If a finite set $E$ is partitioned into subsets $A_1, \dots, A_k$ (pairwise disjoint, with union $E$ ), then

\abs{E} = \abs{A_1} + \abs{A_2} + \dots + \abs{A_k}.

Proposition 27.2 (Multiplication principle)

If an object is built by a succession of $k$ choices, with $n_1$ options for the first choice and, whatever the previous choices, $n_i$ options for the $i$ -th, then the number of objects built is $n_1 \times n_2 \times \dots \times n_k$ .

Proof. Both statements are proved by induction on $k$ ; the case $k = 2$ of the second amounts to counting a rectangular array by rows. ∎

Example 27.3

A restaurant offers 4 starters, 6 mains, 3 desserts: $4 \times 6 \times 3 = 72$ different three-course meals.

27.2 Tuples, permutations, factorials

Definition 27.4 ( $k$ -tuples)

A $k$ -tuple of a set $E$ is an ordered list $(x_1, \dots, x_k)$ of elements of $E$ , repetitions allowed. A $k$ -tuple of distinct elements is an arrangement of $k$ elements of $E$ .

Proposition 27.5

Let $\abs E = n$ . The number of $k$ -tuples of $E$ is $n^k$ . The number of arrangements of $k$ elements of $E$ ( $0 \leq k \leq n$ ) is

n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!},

where $n! = 1 \times 2 \times \dots \times n$ (and $0! = 1$ ) is the factorial of $n$ .

Proof. Multiplication principle: for a $k$ -tuple there are $n$ options at each of the $k$ steps; for an arrangement, $n$ options for $x_1$ , then $n - 1$ for $x_2$ (one element is used), …, $n - k + 1$ for $x_k$ . ∎

Definition 27.6 (Permutation)

A permutation of $E$ is an arrangement of all $n$ elements of $E$ : an ordering of $E$ . By Proposition 27.5 (case $k = n$ ), the number of permutations of an $n$ -element set is $n!$ .

Example 27.7

Five runners can finish a race in $5! = 120$ different orders. The number of possible podiums (first three places) is $5 \times 4 \times 3 = 60$ .

27.3 Combinations and binomial coefficients

Definition 27.8 (Combinations)

A combination of $k$ elements of $E$ is a subset of $E$ with $k$ elements (no order, no repetition). Their number is written $\dbinom{n}{k}$ , read “ $n$ choose $k$ ”.

Theorem 27.9

For $0 \leq k \leq n$ :

\binom{n}{k} = \frac{n!}{k!\,(n-k)!} .

Proof. Count the arrangements of $k$ elements of $E$ in two ways. Directly: $\frac{n!}{(n-k)!}$ . Alternatively, choose first the underlying subset ( $\binom nk$ ways), then order it ( $k!$ ways); the multiplication principle gives $\binom{n}{k}\,k!$ . Equating, $\binom nk = \frac{n!}{k!(n-k)!}$ . ∎

Proposition 27.10 (Basic identities)

For $0 \leq k \leq n$ :

\binom{n}{0} = \binom{n}{n} = 1, \qquad \binom{n}{1} = n, \qquad \binom{n}{k} = \binom{n}{n-k},

and Pascal’s rule: for $1 \leq k \leq n-1$ ,

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.

Proof. The symmetry $\binom nk = \binom{n}{n-k}$ holds because taking complements matches $k$ -element subsets with $(n-k)$ -element subsets, one for one. For Pascal’s rule, fix an element $a \in E$ and sort the $k$ -element subsets into those containing $a$ — obtained by adjoining $a$ to a $(k-1)$ -element subset of $E \setminus \{a\}$ , of which there are $\binom{n-1}{k-1}$ — and those avoiding $a$ , which are the $k$ -element subsets of $E \setminus \{a\}$ , numbering $\binom{n-1}{k}$ . Conclude by the addition principle. ∎

Pascal’s rule generates the coefficients row by row — Pascal’s triangle: each entry is the sum of the two above it.

Pascal’s triangle, rows n = 0 to 5: Pascal’s rule 41 + 42 = 52 in action. — Pascal’s triangle, rows $n = 0$ to $5$ : Pascal’s rule $\binom{4}{1} + \binom{4}{2} = \binom{5}{2}$ in action.

Theorem 27.11 (Binomial theorem)

For all $a, b \in \R$ (or $\C$ ) and $n \in \N$ :

(a+b)^n = \sum_{k=0}^{n} \binom{n}{k}\, a^{k}\, b^{\,n-k} .

Proof. Expand the product $(a+b)(a+b)\cdots(a+b)$ ( $n$ factors): each term of the expansion picks $a$ or $b$ in every factor, producing $a^k b^{n-k}$ where $k$ is the number of factors contributing $a$ . The number of ways to choose these $k$ factors among $n$ is $\binom nk$ , which is therefore the coefficient of $a^k b^{n-k}$ . ∎

Corollary 27.12

$\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n$ and $\displaystyle\sum_{k=0}^{n} (-1)^k\binom{n}{k} = 0$ ( $n \geq 1$ ).

Proof. Take $a = b = 1$ , then $a = -1$ , $b = 1$ in the binomial theorem. The first identity also has a direct meaning: an $n$ -element set has $2^n$ subsets (each element is in or out: multiplication principle), sorted by size. ∎

Method 27.13 (Choosing the right model)

Before counting, answer two questions: does order matter? and are repetitions allowed?

	order matters	order irrelevant
repetitions allowed	$n^k$ (tuples)	(university)
no repetitions	$\frac{n!}{(n-k)!}$ (arrangements)	$\binom nk$ (subsets)

Drawing balls from an urn: with replacement, in order $\to$ tuples; without replacement, in order $\to$ arrangements; a handful all at once $\to$ subsets.

27.4 Exercises

Exercise 27.1 ★

A license plate consists of 2 letters (A–Z), then 3 digits, then 2 letters. How many plates are possible? How many have no repeated character?

Solution

Solution of Exercise 27.1.

Multiplication principle: $26^2 \times 10^3 \times 26^2 = 26^4 \times 10^3 = 456\,976\,000$ .

Without repeated characters, the four letters must be distinct ( $26 \times 25 \times 24 \times 23$ ways, filling the letter positions in order) and the three digits distinct ( $10 \times 9 \times 8$ ):

26 \times 25 \times 24 \times 23 \times 10 \times 9 \times 8 = 358\,800 \times 720 = 258\,336\,000 .

Exercise 27.2 ★

Compute $\dbinom{8}{3}$ , $\dbinom{10}{8}$ , and simplify $\dfrac{\binom{n}{2}}{\binom{n+1}{2}}$ .

Solution

Solution of Exercise 27.2.

$\dbinom83 = \dfrac{8 \times 7 \times 6}{3!} = 56$ ; $\dbinom{10}{8} = \dbinom{10}{2} = \dfrac{10 \times 9}{2} = 45$ ;

\frac{\binom n2}{\binom{n+1}2} = \frac{n(n-1)/2}{(n+1)n/2} = \frac{n-1}{n+1}.

Exercise 27.3 ★

In a class of 30 students, one must elect a committee of 4 students, then a president and a treasurer within the committee (one person cannot hold both offices). How many outcomes are possible?

Solution

Solution of Exercise 27.3.

Choose the committee: $\binom{30}{4}$ ways. Then choose president and treasurer among the 4, in order: $4 \times 3 = 12$ ways. Total

\binom{30}{4} \times 12 = 27\,405 \times 12 = 328\,860 .

Exercise 27.4 ★

Expand $(x + 2)^5$ and $(1 - x)^6$ using the binomial theorem. What is the coefficient of $x^3$ in $(2x + 3)^7$ ?

Solution

Solution of Exercise 27.4.

(x+2)^5 = x^5 + 10x^4 + 40x^3 + 80x^2 + 80x + 32 ,

(1-x)^6 = 1 - 6x + 15x^2 - 20x^3 + 15x^4 - 6x^5 + x^6 .

In $(2x+3)^7$ , the term in $x^3$ is $\binom{7}{3}(2x)^3\,3^4 = 35 \times 8 \times 81\, x^3$ : the coefficient is $22\,680$ .

Exercise 27.5 ★★

A standard poker hand consists of 5 cards from a 52-card deck.

How many hands are there?
How many hands contain exactly one ace? At least one ace?
How many hands are “full houses” (three cards of one rank, two of another)?

Solution

Solution of Exercise 27.5.

1. $\dbinom{52}{5} = 2\,598\,960$ .

2. Exactly one ace: choose it ( $4$ ways) and complete with $4$ non-aces: $4 \times \binom{48}{4} = 4 \times 194\,580 = 778\,320$ . At least one ace: complementary counting, $\binom{52}{5} - \binom{48}{5} = 2\,598\,960 - 1\,712\,304 = 886\,656$ .

3. Choose the rank of the three-of-a-kind ( $13$ ), its suits ( $\binom43 = 4$ ), the rank of the pair ( $12$ remaining), its suits ( $\binom42 = 6$ ): $13 \times 4 \times 12 \times 6 = 3744$ .

Exercise 27.6 ★★

How many anagrams (rearrangements of letters, meaningful or not) does the word MATH have? The word BANANA? (Hint for BANANA: first place the three A’s.)

Solution

Solution of Exercise 27.6.

MATH has 4 distinct letters: $4! = 24$ anagrams.

BANANA has 6 letters: three A’s, two N’s, one B. Choose the positions of the A’s ( $\binom63$ ), then of the N’s among the rest ( $\binom32$ ), the B takes the last spot:

\binom{6}{3}\binom{3}{2} = 20 \times 3 = 60 .

(Equivalently $\frac{6!}{3!\,2!\,1!} = 60$ .)

Exercise 27.7 ★★

Prove the identity $k\dbinom{n}{k} = n\dbinom{n-1}{k-1}$ ( $1 \leq k \leq n$ ) in two ways: by the factorial formula, and by counting in two ways the pairs (committee of $k$ people, its president) chosen from $n$ people.

Solution

Solution of Exercise 27.7.

Algebraically:

k\binom nk = \frac{k\,n!}{k!(n-k)!} = \frac{n!}{(k-1)!\,(n-k)!} = n\,\frac{(n-1)!}{(k-1)!\bigl((n-1)-(k-1)\bigr)!} = n\binom{n-1}{k-1}.

By double counting: count pairs (committee of $k$ , president in it). Either choose the committee ( $\binom nk$ ) then its president ( $k$ ): $k\binom nk$ pairs. Or choose the president first ( $n$ options) then the other $k-1$ members among the remaining $n-1$ : $n\binom{n-1}{k-1}$ pairs.

Exercise 27.8 ★★

A path in the plane goes from $(0,0)$ to $(m, n)$ by unit steps East or North. Show that the number of such paths is $\dbinom{m+n}{m}$ .

Solution

Solution of Exercise 27.8.

A path consists of exactly $m + n$ steps, of which $m$ are East and $n$ are North; it is entirely determined by the set of instants (among the $m+n$ ) at which one steps East. There are $\binom{m+n}{m}$ such choices.

Exercise 27.9 ★★★

Prove Vandermonde’s identity: for $0 \leq k \leq m + n$ ,

\binom{m+n}{k} = \sum_{j=0}^{k} \binom{m}{j}\binom{n}{k-j},

by counting the $k$ -element subsets of a set split into a group of $m$ and a group of $n$ . Deduce that $\displaystyle\sum_{j=0}^{n}\binom{n}{j}^{\!2} = \binom{2n}{n}$ .

Solution

Solution of Exercise 27.9.

Split a set of $m + n$ people into a group $A$ of $m$ and a group $B$ of $n$ . A $k$ -element subset contains some number $j$ of members of $A$ ( $0 \leq j \leq k$ ) and $k - j$ members of $B$ ; for fixed $j$ there are $\binom mj \binom{n}{k-j}$ such subsets, and the addition principle over $j$ gives Vandermonde’s identity.

With $m = n = k$ :

\binom{2n}{n} = \sum_{j=0}^n \binom nj \binom{n}{n-j} = \sum_{j=0}^n \binom nj^{2},

using the symmetry $\binom{n}{n-j} = \binom nj$ .

Exercise 27.10 ★★★

Using the binomial theorem, show that for all $n \geq 1$ ,

\sum_{k=1}^{n} k \binom{n}{k} = n\,2^{n-1}.

(Hint: either differentiate $(1+x)^n$ , or use Exercise 27.7.)

Solution

Solution of Exercise 27.10.

Via Exercise 27.7:

\sum_{k=1}^n k\binom nk = \sum_{k=1}^n n\binom{n-1}{k-1} = n\sum_{j=0}^{n-1}\binom{n-1}{j} = n\,2^{n-1},

by Corollary 27.12. Via differentiation: differentiating $(1+x)^n = \sum_k \binom nk x^k$ gives $n(1+x)^{n-1} = \sum_k k \binom nk x^{k-1}$ ; evaluate at $x = 1$ .

27.5 Problem: The art of counting twice

Problem 27.1

Weekend problem — stars and bars, deranged hats, and identities proved by counting one thing two ways

The deepest trick in combinatorics is disarmingly simple: count the same collection twice, by two different methods, and equate the answers. This problem practices the models of Method 27.13, adds a technique the chapter’s course did not need — the stars and bars of ice-cream counting — then counts the famous deranged hats exactly, and finds the number $\frac1\eu$ waiting at the bottom of the hat pile, its third appearance in this book.

Part I — Choosing the model.

Count the license plates made of $2$ letters followed by $3$ digits; then the anagrams of BANANA.
From a $32$ -card deck, count the $5$ -card hands; then the hands containing exactly $2$ of the $4$ aces.
A robot walks from $(0,0)$ to $(4,3)$ using only unit steps right or up: how many paths? (Encode a path as a word in R and U.)
Expand $(1 + x)^4$ by the binomial theorem (Theorem 27.11); then evaluate at $x = 1$ and $x = -1$ : which two identities about the numbers $\binom nk$ drop out?
Prove by double counting that $k\binom nk = n\binom{n-1}{k-1}$ (count committees-with-chair two ways), and deduce $\sum_{k=0}^{n} k\binom nk = n\,2^{n-1}$ .

Part II — Stars and bars.

An ice-cream shop sells $4$ flavors; you order $10$ scoops (flavors may repeat, order in the cup is irrelevant). Encode an order as a row of $10$ stars (scoops) separated by $3$ bars (flavor changes), and count the orders.
Count the triples of nonnegative integers with $x + y + z = 12$ .
Count the triples of positive integers with $x + y + z = 12$ (substitute $x = 1 + x'$ , etc.).
How many distinct monomials appear in the expansion of $(a + b + c)^5$ ?
Sanity check the method: count the orders of $3$ scoops from $2$ flavors with the formula, then list them all and compare.
Say exactly where “scoops are identical” entered the encoding — and count what happens instead if the scoops are eaten in order (distinct positions), with Method 27.13’s checklist.

Part III — The deranged hats. A derangement is a redistribution of $n$ hats to their $n$ owners in which nobody receives their own hat; let $D_n$ count them. (Problem 18.1 showed that one guest on average recovers their own hat — now we count the fully unlucky parties exactly.)

Compute $D_1$ , $D_2$ , $D_3$ by listing, and $D_4$ patiently (or cleverly).
Justify the recurrence $D_n = (n - 1)\left(D_{n-1} + D_{n-2}\right)$ : guest 1 receives some hat $k \neq 1$ ( $n - 1$ choices); split according to whether guest $k$ receives hat 1 or not. Check it reproduces $D_4$ , and compute $D_5$ .
For $n = 3$ , prove by inclusion–exclusion (subtract the assignments fixing at least one hat, add back the overcounts) that $D_3 = 3!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}\right)$ , and state the general formula.
Compute $\frac{D_5}{5!}$ and compare with $\frac1\eu \approx 0.3679$ : the probability that a large shuffled party deranges completely is $\frac1\eu$ — the third cameo of this constant, after the lottery and the secretary of Problem 23.1. (Why: the formula of question 14 is the beginning of a famous series for $\eu^{-1}$ , told in the university volumes.)
Secret Santa among $10$ friends: names are drawn uniformly at random. What is the probability the draw is valid (nobody draws themselves), and how many redraws should the group expect?

Part IV — Counting twice, winning twice.

The handshake lemma: at any party, summing over guests the number of hands each shook counts every handshake exactly twice. Deduce that the number of guests who shook an odd number of hands is always even — and check the claim makes sense at a three-guest party.
Prove the jewel $1^3 + 2^3 + \dots + n^3 = (1 + 2 + \dots + n)^2$ by induction, and verify it for $n = 3$ . (Little Gauss’s sum, squared, counts cubes.)
Vandermonde’s identity (Exercise 27.9) via paths: interpret $\binom{2n}{n}$ as lattice paths of question 3’s kind from $(0,0)$ to $(n,n)$ , cut each path at its crossing of the anti-diagonal, and explain how $\sum_j \binom nj^2$ appears.
Finale — the counter’s four moves, one line each with an example from this problem: multiply stages and add cases; encode cleverly (stars and bars, path words); count the same thing twice (committee-with-chair, handshakes); subtract the unwanted and correct the overcounts (derangements). And note where the counting goes to work next: probability, and the paths of the matrices-and-graphs chapter.

Solution

Solution of Problem 27.1.

1. $26^2 \times 10^3 = 676\,000$ plates. BANANA: $6$ letters with A tripled and N doubled: $\frac{6!}{3!\,2!} = 60$ anagrams.

2. $\binom{32}{5} = 201\,376$ hands; $\binom42 \binom{28}{3} = 6 \times 3\,276 = 19\,656$ with exactly two aces.

3. A path is a word with $4$ R’s and $3$ U’s: choose the U positions: $\binom73 = 35$ .

4. $(1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4$ . At $x = 1$ : $\sum_k \binom nk = 2^n$ ; at $x = -1$ : $\sum_k (-1)^k \binom nk = 0$ — row sums and alternating row sums of Pascal’s triangle.

5. Committees of $k$ people with a chair, from $n$ : choose the committee then its chair ( $\binom nk \times k$ ), or the chair then the other members ( $n \times \binom{n-1}{k-1}$ ): equal. Summing over $k$ : the right side sums to $n \sum_j \binom{n-1}{j} = n\,2^{n-1}$ .

6. A row of $10$ stars and $3$ bars encodes the order (scoops of flavor 1 before the first bar, etc.); the row has $13$ symbols and is determined by the bar positions: $\binom{13}{3} = 286$ orders.

7. $12$ stars, $2$ bars: $\binom{14}{2} = 91$ .

8. With $x', y', z' \geq 0$ and $x' + y' + z' = 9$ : $\binom{11}{2} = 55$ .

9. A monomial $a^i b^j c^k$ with $i + j + k = 5$ : $\binom72 = 21$ .

10. Formula: $3$ stars, $1$ bar: $\binom41 = 4$ ; list: $(3,0)$ , $(2,1)$ , $(1,2)$ , $(0,3)$ : agreement.

11. “Identical” entered when an order was declared to be nothing but the counts per flavor — the stars carry no names. If the scoops are eaten in order, each of the $10$ distinct positions picks a flavor freely: $4^{10} = 1\,048\,576$ sequences — a different model and a different world (Method 27.13: always ask ordered? distinct? repetition allowed?).

12. $D_1 = 0$ ; $D_2 = 1$ (swap); $D_3 = 2$ (the two $3$ -cycles); $D_4 = 9$ .

13. Guest 1 gets hat $k \neq 1$ : $n - 1$ choices. If guest $k$ gets hat 1, the remaining $n - 2$ guests derange their own hats: $D_{n-2}$ ways. If guest $k$ does not get hat 1, relabel hat 1 as guest $k$ ’s forbidden hat: the $n - 1$ remaining guests derange: $D_{n-1}$ ways. Hence $D_n = (n-1)(D_{n-1} + D_{n-2})$ . Check: $D_4 = 3(2 + 1) = 9$ ; and $D_5 = 4(9 + 2) = 44$ .

14. Of the $3! = 6$ assignments, subtract those fixing at least one hat: three fix a given hat ( $2!$ each, $3 \times 2 = 6$ ), overcounting the pairs ( $3$ pairs, $1!$ each) which must return, and re-subtracting the identity ( $1$ ): $D_3 = 6 - 6 + 3 - 1 = 2$ , i.e. $3!\left(1 - 1 + \frac12 - \frac16\right) = 2$ . In general $D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}$ .

15. $\frac{D_5}{120} = \frac{44}{120} \approx 0.3667$ , already close to $\frac1\eu \approx 0.3679$ : the alternating sum $1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \dots$ marches to $\eu^{-1}$ . A large party’s hats derange about $36.8\,\%$ of the time — the lottery’s and the secretary’s constant, third sighting.

16. $\P(\text{valid}) = \frac{D_{10}}{10!} \approx 0.368$ . Each redraw succeeds with probability $\approx \frac1\eu$ , so the expected number of draws is about $\eu \approx 2.7$ : budget three hat-passings.

17. Each handshake contributes $2$ to the total degree count, so the sum of all guests’ handshake-numbers is even. A sum of integers is even only if the number of odd terms is even: odd-shakers come in even numbers. (At three guests: possible handshake profiles never have exactly one or three odd entries — check the four possible graphs.)

18. $n = 1$ : $1 = 1$ . If $1^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ , adding $(n+1)^3$ :

\frac{n^2(n+1)^2}{4} + (n+1)^3 = \frac{(n+1)^2\left(n^2 + 4n + 4\right)}{4} = \left(\frac{(n+1)(n+2)}{2}\right)^{\!2} :

heredity. For $n = 3$ : $1 + 8 + 27 = 36 = 6^2$ .

19. A path to $(n, n)$ makes $2n$ steps and crosses the anti-diagonal $x + y = n$ at exactly one lattice point $(j, n - j)$ ; the first half is a path with $j$ R’s among $n$ steps ( $\binom nj$ choices), the second half, read backwards, likewise ( $\binom nj$ again, by symmetry). Summing over the crossing point: $\binom{2n}{n} = \sum_j \binom nj^2$ — Vandermonde’s identity, drawn.

20. Multiply stages, add cases: plates and poker hands. Encode: paths as RU-words, orders as stars and bars. Count twice: committees-with-chair, handshakes, mid-cut paths. Subtract and correct: the deranged hats, with $\frac1\eu$ as the residue. Next stops: these counts under probability’s fractions, and the path-counting powers of the adjacency matrices two chapters ahead.