Permutations and Combinations

To count arrangements or selections without listing them, use two principles (add for "or", multiply for "and then") and two questions about the objects: does order matter, and is repetition allowed. Permutations count ordered arrangements, combinations count unordered selections, and the remaining cases (identical objects, circular seating, restrictions such as "together" or "never adjacent", distributions, grid paths) are these with a correction.

The skill is choosing the right model and avoiding the double count or the forgotten case. A decision table, the standard corrections with a reason for each, and worked examples follow.

Order test. Swap two chosen items. If the outcome changes (a different PIN, a different seating, president and secretary swapped), order matters and the count is a permutation. If nothing changes (the same committee, the same hand of cards), it is a combination.

Identities used below. $\binom{n}{r} = \binom{n}{n-r}$; $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ (Pascal); $\sum_{r=0}^{n} \binom{n}{r} = 2^n$; $^{n}P_{r} = r! \binom{n}{r}$.

Permutations. The first position has $n$ options, the second $n - 1$, and so on for $r$ positions, so by the product rule $^{n}P_{r} = n(n-1)\cdots(n-r+1) = n!/(n-r)!$.

Combinations from permutations. Each unordered selection of $r$ objects appears $r!$ times among the ordered selections, once per ordering. Dividing, $\binom{n}{r} = {^{n}P_{r}}/r!$.

Identical objects. If $n_1$ objects are identical, the $n_1!$ orderings among them give the same visible arrangement, so each visible arrangement is counted $n_1!$ times in $n!$. Dividing by each $n_i!$ gives the multiset formula.

Circular seating. The $n!$ linear orders fall into groups of $n$ rotations that give the same seating, so there are $n!/n = (n-1)!$ seatings.

Stars and bars. Write the $n$ identical items as stars and separate the $k$ people's shares with $k - 1$ bars. Every arrangement of $n$ stars and $k - 1$ bars in a row is one distribution, so the count is $\binom{n + k - 1}{k - 1}$. If each person must get at least one item, hand one to each first and distribute the remaining $n - k$: $\binom{n - 1}{k - 1}$.

Grid paths. A path from $(0, 0)$ to $(a, b)$ using unit steps right and up is a word of $a$ R's and $b$ U's, so there are $\binom{a + b}{a}$ paths. Paths through a point $P$ multiply the counts before and after $P$.

Divisors. If $N = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$, a divisor chooses an exponent from $0$ to $e_i$ for each prime, giving $(e_1 + 1)(e_2 + 1)\cdots(e_k + 1)$ divisors.

Related material. A derangement is a permutation with no element in its original place. Inclusion-exclusion gives $D_n = n! \sum_{i=0}^{n} (-1)^i / i!$; the first values are $D_1 = 0$, $D_2 = 1$, $D_3 = 2$, $D_4 = 9$, $D_5 = 44$.

Example 1 (product rule with and without repetition). A code is 3 letters (A to Z, repetition allowed) followed by 2 digits that must differ. Letters: $26^3 = 17576$. Digits: $10 \times 9 = 90$. Codes: $17576 \times 90 = 1581840$.

Example 2 (identical letters). Arrangements of the letters of LETTER: 6 letters with E twice and T twice, so $\frac{6!}{2!\,2!} = \frac{720}{4} = 180$.

Example 3 (at least). A committee of 5 is chosen from 6 men and 4 women, with at least 2 women.

Example 4 (circle with a pair). Seven people sit round a table.

Example 5 (gap method). Five boys and three girls stand in a row with no two girls adjacent.

Example 6 (leading zero). How many 4-digit even numbers have all digits distinct?

Example 7 (stars and bars). Ten identical sweets go to 4 children.

Example 8 (grid paths). Paths from $(0, 0)$ to $(4, 3)$ with unit steps right or up: $\binom{7}{3} = 35$. Through $(2, 2)$: $\binom{4}{2} \times \binom{3}{1} = 6 \times 3 = 18$.

Example 9 (geometry counts). A decagon has $\binom{10}{2} - 10 = 35$ diagonals (pairs of vertices minus sides), which is $\frac{n(n-3)}{2}$ with $n = 10$. Twelve people shaking hands once each make $\binom{12}{2} = 66$ handshakes.

Example 10 (divisors). $360 = 2^3 \times 3^2 \times 5$ has $(3+1)(2+1)(1+1) = 24$ divisors.

Example 11 (derangements). Four letters are put in four addressed envelopes so that no letter is in its own envelope: $D_4 = 9$ ways out of $4! = 24$.

Example 12 (block method: letters together). In how many arrangements of GARDEN are the vowels A and E together? Glue them into one block: the block and G, R, D, N make 5 units, arranged in $5! = 120$ ways, and the block can be AE or EA: $120 \times 2 = 240$. Out of $6! = 720$ arrangements, so the vowels are apart in $720 - 240 = 480$.

Example 13 (dictionary rank). If all arrangements of the letters of RAIN are listed in dictionary order, what is the position of RAIN? Letters in order: A, I, N, R.

Example 14 (distinct objects into distinct boxes, none empty). In how many ways can 4 different balls go into 3 different boxes with no box empty? All assignments: $3^4 = 81$. Subtract those missing a given box: $3 \times 2^4 = 48$; add back those missing two boxes: $3 \times 1^4 = 3$. Answer: $81 - 48 + 3 = 36$. The slip $3^4 = 81$ allows empty boxes. A second route as a check: one box gets 2 balls ($\binom{4}{2} = 6$ ways to pick them, 3 choices of box) and the other two balls fill the remaining boxes in $2$ ways: $6 \times 3 \times 2 = 36$.