Counting: Permutations and Combinations

Counting is the foundation of discrete probability. To find the chance of something, you often just count the favorable outcomes, count the total outcomes, and divide. The hard part is counting large sets without listing them one by one, and two ideas do almost all of that work: permutations (when order matters) and combinations (when it doesn't). Both grow out of a single rule.

The multiplication rule

If a task is built from a sequence of independent steps, and step 1 can be done $n_1$ ways, step 2 in $n_2$ ways, and so on, then the whole task can be done in

$$n_1 \times n_2 \times \cdots \times n_k$$

ways. Every choice at one step gets paired with every choice at the next, so the counts multiply. This is why a menu with 3 starters and 2 mains offers $3 \times 2 = 6$ different meals.

Permutations: order matters

A permutation counts arrangements, where swapping two items gives a genuinely different result. The number of ways to line up all $n$ distinct items is

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

read "$n$ factorial." (The first spot has $n$ candidates, the next has $n-1$ left, and so on, straight from the multiplication rule.) If you only fill $r$ of the $n$ spots, you stop early:

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

Here $n$ is the number of available items and $r$ is the number of ordered positions. By convention $0! = 1$.

Combinations: order doesn't matter

A combination counts selections, where a group is the same no matter what order you picked it in. To choose $r$ items from $n$:

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

read "$n$ choose $r$." The logic: start from the ordered count $P(n,r)$, then divide by $r!$ to erase the orderings, since each unordered group of $r$ items was counted $r!$ times, once for each way of arranging it. That single division is the whole difference between a permutation and a combination.

Worked example

A desk of 5 traders needs a team. First, how many ways can you pick a 2-person team where the two roles are the same? Order does not matter, so use a combination:

$$\binom{5}{2} = \frac{5!}{2!\,3!} = \frac{5 \times 4}{2 \times 1} = \frac{20}{2} = 10 .$$

Ten possible teams. Now suppose the two roles are different, say a lead and a backup. Order now matters, so use a permutation:

$$P(5, 2) = \frac{5!}{3!} = 5 \times 4 = 20 .$$

Twenty possibilities, exactly $2! = 2$ times the combination count, because each of the 10 teams can be arranged into lead-and-backup in 2 ways. That factor of $r!$ is the entire relationship between the two.

Common pitfalls

• Order matters, or it doesn't. Deciding this first is the whole game. "How many teams?" is a combination; "how many rankings?" is a permutation. Using the wrong one is off by exactly a factor of $r!$.
• With or without replacement. Drawing cards without replacement shrinks the pool each step ($52, 51, 50, \dots$); rolling a die with replacement does not ($6, 6, 6, \dots$). Match the formula to the setup.
• "And" multiplies, "or" adds. Sequential choices that all happen multiply their counts; mutually exclusive alternatives add. Mixing these up is the most common counting error.
• Silent double-counting. Whenever items are interchangeable, ask whether you've counted the same outcome more than once and divide out the symmetry, just as $\binom{n}{r}$ divides by $r!$.

These counts are the raw material for probability: the "choose" coefficient $\binom{n}{r}$ is exactly what turns a single yes/no trial into the The Binomial Distribution, and every classic equally-likely-outcomes problem reduces to a favorable count over a total count. Pair careful counting with Conditional Probability and most interview brainteasers fall apart.