Permutations and Combinations

A permutation is simply an arrangement, where order matters (who gets gold, silver and bronze), and a combination is a plain selection, where it doesn't (who's on the committee). "Permute" means to rearrange, which is where the first name comes from; "combination" just means a group put together. They're good for odds of all kinds, from lotteries to poker hands. The formulas look heavy with all the exclamation marks, but $n!$ just means $n \cdot (n-1) \cdots 2 \cdot 1$ (every way to line up $n$ things). $P(n, k) = \frac{n!}{(n-k)!}$ is lining up $k$ of them (the leftover $(n-k)!$ cancels the part you don't use), and $\binom{n}{k}$ divides that by one more $k!$ (because when order doesn't matter, each group was counted once per ordering). It's just the product rule plus one division.

Remember the PIN with no repeated digits from last lesson: 10 choices, then 9, then 8, then 7. The count shrinks by one at each stage because each pick uses something up. That pattern shows up so often it gets its own name.

Permutations. Hand out gold, silver and bronze among 8 runners. There are 8 choices for gold, then 7 left for silver, then 6 for bronze, so $P(8, 3) = 8 \cdot 7 \cdot 6 = 336$. If you keep going until everything's placed, all $n$ items in a row can be arranged in $n \cdot (n-1) \cdots 1 = n!$ ways. The formula $\frac{n!}{(n-k)!}$ is just that product with the unused tail $(n-k)!$ cancelled off.

Combinations. Now pick a 3-person committee from 10 people. A committee doesn't care about order: Ana, Ben, Cy is the same committee as Cy, Ana, Ben. So what can we do? Count as if order mattered, $10 \cdot 9 \cdot 8 = 720$, and then think about how many times each committee got counted. Its 3 members can be lined up in $3! = 6$ orders, and the ordered count included every one of them. So each committee was counted 6 times, and $\binom{10}{3} = 720 / 6 = 120$.

Symmetry. Choosing $k$ people to include is the same as choosing the $n - k$ to leave out, so $\binom{n}{k} = \binom{n}{n-k}$. You'll see that symmetry in the picture below.

Is order relevant? Ask whether swapping two chosen items gives a different outcome. Podium places: yes, so it's a permutation. A hand of cards: no, so it's a combination. A lottery ticket: no, which is why the odds of choosing 6 numbers from 49 are 1 in $\binom{49}{6} = 13{,}983{,}816$.

A common mistake. It's tempting to use a combination whenever a problem says "choose," because that's the word in "n choose k." It isn't the word that decides, it's whether order changes the outcome. "Choose a president and a treasurer" gives different outcomes when you swap the two people, so that's a permutation even though it says "choose."

Lottery odds, poker hand probabilities and the number of possible test schedules are all counted with permutations and combinations.