You have almost certainly met permutations and combinations before as two formulas to plug numbers into. This page rebuilds them from the product rule, so that you never have to remember which formula is which again — you derive the one you need on the spot. The single question that separates them is: does order matter?

Arranging 3 runners on a podium — gold, silver, bronze — order matters: Alice-then-Bob is a different result from Bob-then-Alice. That is a permutation. Choosing 3 people for a committee — order does not matter: the committee \{Alice, Bob, Carol\} is one committee however you list its members. That is a combination. Same people, same three — different counts, because one problem cares about order and the other refuses to.

Factorials and permutations, from the product rule

Arrange all n distinct things in a row. Fill the first slot n ways, the next n-1 ways (one is used up), then n-2, down to 1. The product rule multiplies these:

the factorial of n. There are 5! = 120 ways to seat five people in a row; the whole thing is just the product rule with a shrinking supply. We define 0! = 1 — there is exactly one way to arrange nothing, the empty arrangement — and this convention makes every formula below come out right.

Arrange only k of the n. Fill k slots: n, then n-1, … , down to n-k+1 — a run of k descending factors. That is the number of permutations of n things taken k at a time:

The fraction is just bookkeeping: n! counts full arrangements, and dividing by (n-k)! cancels the arrangements of the n-k things we never picked. So the podium of 3 from 8 runners is P(8,3) = 8 \cdot 7 \cdot 6 = 336.

Combinations: divide out the order you don't want

Now suppose order should not count. Start from the ordered count P(n,k) and notice it has overcounted: each unordered choice of k things was counted once for every way of ordering those k things — and there are k! such orderings. Divide the overcount away:

This is the binomial coefficient "n choose k", also written C(n,k) — the number of k-element subsets of an n-element set. The committee of 3 from 8 is \binom{8}{3} = \frac{8 \cdot 7 \cdot 6}{3!} = \frac{336}{6} = 56. The divide-out-the-order move is the whole idea: permutations count arrangements, combinations count arrangements and then quotient by the k! re-orderings that we chose not to distinguish.

The shape of the binomial coefficients

Fix n and let k run from 0 to n. The counts \binom{n}{k} rise to a peak in the middle and fall back — and they are perfectly symmetric, because \binom{n}{k} = \binom{n}{n-k}. The extremes are tiny: \binom{n}{0} = \binom{n}{n} = 1 (one way to choose everything or nothing). Drag n and watch the hump grow and stay balanced.

Add across any row and you get \sum_{k=0}^{n} \binom{n}{k} = 2^n — the total number of subsets of an n-set, sorted by size. That is the same 2^n we got by the yes/no product-rule argument, now split into its size-k pieces. The rows are exactly Pascal's triangle, and each entry is the sum of the two above it: \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} — pick a fixed element, and either it is in your subset (choose k-1 more from the rest) or it is out (choose all k from the rest).

Worked examples

Anagrams with repeats

How many distinct arrangements of the letters of BANANA? Six letters, so 6! if they were all different — but they are not: the 3 A's are identical, and the 2 N's are identical. Every distinct word was counted 3! times (re-orderings of the A's) and 2! times (the N's), so divide those out:

This "divide by the factorials of the repeat-counts" is the multinomial coefficient — the star of the next page. It is the same reflex as combinations: overcount, then quotient by the symmetries you don't want to see.

Handshakes

At a party of n people everyone shakes hands once with everyone else. A handshake is an unordered pair, so the count is \binom{n}{2} = \frac{n(n-1)}{2}. For n = 10 that is 45 — and it is exactly the number of edges in a complete graph, a fact the last page of this module will lean on hard.