Permutations and combinations

Eight runners are in a race. How many different ways can the gold, silver and bronze medals be given out?

Fill the places one at a time:

• Gold: any of the 8 runners, so 8 choices.
• Silver: anyone except the gold winner, so 7 choices.
• Bronze: anyone except those two, so 6 choices.

For each of the 8 golds there are 7 silvers, and for each of those, 6 bronzes. So the total is

$8 \times 7 \times 6 = 336.$

This is the multiplication principle: if you make several choices one after another, multiply the number of options at each step.

Multiplying down to 1 happens so often that it has a symbol. $n!$, read "$n$ factorial", means

$n! = n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1.$

For example, $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$. That's the number of ways to arrange 5 different books in a row: 5 choices for the first spot, 4 for the next, and so on.

By agreement, $0! = 1$. (There is exactly one way to arrange nothing: do nothing.) This keeps the formulas below working when $r = n$ or $r = 0$.

Now choose a team of 3 from the 8 runners. There are no medals: the team $\{\text{Ali, Bo, Cy}\}$ is the same team as $\{\text{Cy, Ali, Bo}\}$.

The podium count, 336, counts every team many times over: once for each way of ordering its 3 members. Three people can be ordered in $3! = 6$ ways. So

$\text{number of teams} = \frac{336}{6} = 56.$

That's the whole idea behind combinations: count as if order mattered, then divide by the number of orders each group has been counted in.

To decide which to use, imagine swapping two of the chosen items. Do you get a different outcome?

Roles, positions or a sequence mean order matters. A group, set or hand means it doesn't.