Permutations and combinations, with and without repetition

Two rules underneath everything

Almost every counting question rests on two rules, both listed in the Bocconi syllabus.

• Product rule. If a task is done in stages, with $a$ ways for the first stage and $b$ ways for the second whatever happened in the first, the whole task can be done in $a \times b$ ways. A menu with 4 starters and 5 main courses gives $4 \times 5 = 20$ two-course meals.
• Sum rule. If a choice falls into separate cases that cannot happen together, add the counts of the cases. A meal that is either one of 4 starters or one of 5 mains (but not both) can be chosen in $4 + 5 = 9$ ways.

The word that signals each rule is worth hearing: "and then" means multiply; "or, one case or the other" means add.

Factorials

The number of ways to put $n$ different objects in a row is

$$n! = n \times (n-1) \times \dots \times 2 \times 1,$$

by the product rule: $n$ choices for the first place, $n-1$ for the second, and so on. By convention $0! = 1$. Learn the small values by heart, since there is no calculator on the test: $3! = 6$, $4! = 24$, $5! = 120$, $6! = 720$, $7! = 5040$.

The two questions

Before you write any formula, answer two questions about the selection of $k$ items from $n$ kinds.

1. Does order matter? A president and a secretary are different jobs, so choosing Ada then Ben differs from Ben then Ada: order matters. A two-person committee is the same committee whichever name you say first: order does not matter.
2. Can an item be chosen more than once? Digits in a code can repeat; people on a committee cannot.

The answers place you in one cell of this table.

	No repetition	Repetition allowed
Order matters	$\dfrac{n!}{(n-k)!}$	$n^k$
Order does not matter	$\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$	$\dbinom{n+k-1}{k}$

Where the formulas come from

Ordered, no repetition (permutations of $k$ out of $n$): $n$ choices for the first place, $n-1$ for the second, down to $n-k+1$ for the $k$-th. Multiply only those $k$ factors; you rarely need the factorial form. Choosing a winner, a runner-up and a third place among 8 finalists gives $8 \times 7 \times 6 = 336$.

Ordered, with repetition: each of the $k$ places has all $n$ options, so $n^k$. A three-letter code from the letters A to E, repeats allowed, can be written in $5^3 = 125$ ways.

Unordered, no repetition (combinations): count the ordered selections, then divide by the $k!$ orders in which each group was counted. That is why $\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!}$. Two facts make the arithmetic short: $\binom{n}{k} = \binom{n}{n-k}$ (choosing who is in is the same as choosing who is out), and $\binom{n}{1} = n$, $\binom{n}{2} = \frac{n(n-1)}{2}$.

Unordered, with repetition: picture the $k$ chosen items as stars and the borders between the $n$ kinds as $n-1$ bars. Every selection is one row of $k$ stars and $n-1$ bars, so the count is the number of ways to choose which of the $k + n - 1$ places hold stars: $\binom{n+k-1}{k}$. Buying 2 fruits from apples and pears gives $\binom{3}{2} = 3$: two apples, one of each, two pears.

Arrangements with identical objects

If some of the $n$ objects in a row are identical, swapping two identical ones creates no new arrangement. Divide $n!$ by the factorial of each group of repeats:

$$\frac{n!}{a!\,b!\,\cdots}$$

The letters of NOON give $\frac{4!}{2!\,2!} = 6$ arrangements, which you can list: NNOO, NONO, NOON, ONNO, ONON, OONN.

Checking without a calculator

Use a second route whenever you can. A combination should equal the matching permutation divided by $k!$; an arrangement with repeats can be rebuilt by choosing positions group by group; a stars-and-bars answer can be checked on a tiny case you can list. If the two routes disagree, one of them has counted the same thing twice.