Permutations and Combinations

Before you can compute the odds of anything — a poker hand, a coin-flip streak, the number of up-down paths a binomial tree can take — you first have to count the possibilities. Not estimate, count exactly. Do it by hand for anything beyond a handful of items and you will still be listing cases at midnight. Permutations and combinations are the two formulas that let you skip the listing.

The analogy: a race versus a committee

Ten runners enter a race. First, second, and third place get medals. How many ways can the medals be handed out? Order matters here — Alice-Bob-Carol (gold-silver-bronze) is a completely different outcome from Bob-Alice-Carol. This is a permutation: an ordered selection.

Now instead: ten candidates apply, and three are chosen for a committee. There is no gold, silver, or bronze — Alice-Bob-Carol and Bob-Alice-Carol are the same committee. Order doesn't matter. This is a combination: an unordered selection.

Same ten people, same group of three chosen, wildly different counts — because one question cares about arrangement and the other only cares about membership.

Writing it down

Start with factorial: $n!$ (n factorial) means "arrange $n$ distinct items in a line," and it equals $n \times (n-1) \times (n-2) \times \cdots \times 1$. Five books on a shelf can be ordered $5! = 5\times4\times3\times2\times1 = 120$ ways, because there are 5 choices for the first slot, 4 remaining for the second, and so on. Define $0! = 1$ — an empty shelf has exactly one arrangement: nothing.

Permutations. Choosing and ordering $r$ items out of $n$:

$$P(n,r) = \frac{n!}{(n-r)!}.$$

In words: count all $n!$ full orderings, then divide out the $(n-r)!$ ways of arranging the items you didn't pick, since their order never got recorded. For the ten-runner race, $P(10,3) = \frac{10!}{7!} = 10\times9\times8 = 720$ ways to assign gold, silver, bronze.

Combinations. Choosing $r$ items out of $n$ with order thrown away:

$$C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}.$$

In words: take the permutation count and divide by $r!$, because every group of $r$ people was counted once for each of the $r!$ ways to order them, and we only want to count it once. For the ten-candidate committee, $\binom{10}{3} = \frac{720}{3!} = \frac{720}{6} = 120$ — six times smaller than the permutation count, because $3! = 6$ orderings collapse into each committee.

The explorer above isn't about combinatorics by name, but drag its parameters and watch how fast a curve's output grows as the input grows — the same intuition applies to $n!$ against $n$. Factorials outrun any polynomial or exponential you can name, which is exactly why $52!$ (the number of ways to shuffle a deck) is a number with 68 digits, and why combinatorial counts explode long before $n$ gets large.

Worked example 1: a five-card poker hand

How many distinct 5-card hands are there from a 52-card deck, and how many of them are a full house (three of one rank, two of another)?

All hands. Order doesn't matter — a hand is a set of 5 cards. So it's a combination:

$$\binom{52}{5} = \frac{52!}{5!\,47!} = \frac{52\times51\times50\times49\times48}{120} = 2{,}598{,}960.$$

Full houses. Build one step by step. Choose the rank that will have three cards: 13 ways. Choose which 3 of its 4 suits: $\binom{4}{3}=4$ ways. Choose the rank that will have two cards (any of the 12 remaining ranks): 12 ways. Choose which 2 of its 4 suits: $\binom{4}{2}=6$ ways. Multiply, because each choice is independent:

$$13 \times 4 \times 12 \times 6 = 3{,}744.$$

So the probability of a full house is $3{,}744 / 2{,}598{,}960 \approx 0.144\%$ — about 1 in 694 hands. Every poker-odds table you have ever seen was built from exactly this kind of step-by-step multiplication.

Worked example 2: counting paths in a binomial tree

Price a stock with a 5-step binomial tree: each step it goes up (U) or down (D). How many distinct paths land on "2 ups, 3 downs" — and what does that have to do with the coefficients above?

A path is a sequence like UDDUD — order matters within the sequence, but we're not asking to distinguish which specific step was "the first up," only how many of each letter appear. That's exactly $\binom{5}{2}$: choose which 2 of the 5 time-slots are the "up" moves (the rest are automatically "down"):

$$\binom{5}{2} = \frac{5!}{2!\,3!} = 10.$$

List them to check: UUDDD, UDUDD, UDDUD, UDDDU, DUUDD, DUDUD, DUDDU, DDUUD, DDUDU, DDDUU — ten paths, matching. This is precisely why the binomial option-pricing formula has a $\binom{n}{k}$ term in it: it's counting how many of the $2^n$ total price paths produce $k$ up-moves, and every path with the same number of ups ends at the same terminal stock price, so their probabilities get grouped together by this coefficient.

What this means in practice

• Probability denominators. "How many total outcomes" is almost always a permutation or combination count, and getting order-matters-or-not backwards silently inflates or shrinks every probability you compute from it by a large factor.
• Binomial and multinomial models. Binomial option pricing, bootstrap resampling, and hypergeometric tests for A/B significance all lean on $\binom{n}{k}$ as the path- or sample-counting term.
• Interview brainteasers. Nearly every "how many ways can you arrange/select/deal" question is testing whether you notice which of the two formulas applies — the arithmetic is the easy part.
• Sanity-checking simulations. If a Monte Carlo estimate of a combinatorial probability disagrees wildly with the exact $\binom{n}{k}$ calculation, trust the exact count and go find the simulation bug.