Combinatorics

Combinatorics answers the question "in how many ways?" before anyone can start listing cases. It is also a prerequisite for classical probability: to divide the number of favourable outcomes by the number of all of them, you first have to be able to count both.

The rule of product

All of combinatorics grows out of a single observation. If a choice is made in several independent steps offering $k_1, k_2, \ldots, k_m$ options, then the number of outcomes is:

The counts are multiplied, not added — because every decision in the first step can be paired with every decision in the second.

Factorials

The product of the first few naturals turns up so often in counting that it has its own symbol:

It is read "n factorial". The first few values are worth knowing by heart:

Mind the first column: $0! = 1$, by definition. An empty sequence can be arranged in exactly one way — by doing nothing — and besides, without that convention the combination formula would divide by zero.

That growth is a practical hint: if ten people can be ordered in $3{,}628{,}800$ ways, solving a problem by listing cases is out of the question.

Permutations

A permutation is an ordering of all $n$ items. The first position can be filled in $n$ ways, the second in $n-1$ (one item is already used), and so on:

Arrangements without repetition

When only $k$ of the $n$ items are chosen but order matters, we are counting arrangements without repetition:

The second form is the handier one to compute: it is simply $k$ decreasing factors starting at $n$.

Arrangements with repetition

If items may repeat, each of the $k$ steps has the full $n$ options, so the rule of product gives directly:

Combinations

When $k$ items are chosen out of $n$ and order does not matter, we have combinations:

Where does the $k!$ in the denominator come from? From the fact that the arrangements counted every $k$-element set $k!$ times over — once for each ordering of the same items. So we divide by the number of those orderings:

Symmetry

Combinations have a property that saves a great deal of arithmetic:

Choosing $k$ items is, after all, the same as naming the $n-k$ items left behind. So $\binom{20}{18}$ is computed like $\binom{20}{2} = 190$, rather than by writing out eighteen factors.

The bars add up to $64 = 2^6$ — the number of subsets of a six-element set, because every item is decided independently: take it or leave it.

Which formula to use

The whole difficulty comes down to two questions about the problem:

A practical test for the first question: swap two of the chosen items. If that gives a different situation, order matters.

Exercises

The five kinds of question match the five formulas in this lesson. A prompt with an exclamation mark asks straight for a factorial — mind $0! = 1$. Permutations for a given $n$ is also $n!$, only phrased in words. Arrangements without repetition and arrangements with repetition both come with $n$ and $k$; they differ only in whether items may be taken more than once. Combinations ask for a choice of $k$ out of $n$ with order ignored — and here the symmetry is worth remembering. Every answer is a whole number.

Common mistakes

• Adding instead of multiplying — successive steps of a choice multiply the counts.
• Confusing arrangements with combinations — if order does not matter, the result still has to be divided by $k!$.
• Forgetting $0! = 1$ — especially in the edge cases of the combination formula.
• Cancelling factorials by eye — $\tfrac{8!}{5!}$ is $8 \cdot 7 \cdot 6$, not $\tfrac{8}{5}$ and not $3!$.
• Assuming repetition — whether items may repeat is decided by the problem, not by which formula is more convenient.
• Listing the cases — beyond $n = 5$ there are usually far too many to get through without a slip.