Permutations and combinations

01When does swapping people change the answer?

Choose a speaker below, then a different recorder. The letter on each card stays with that person; it does not name a job. Once both places are filled, press Swap jobs and watch the names under the two job labels.

Ada as speaker and Ben as recorder is a different assignment from Ben as speaker and Ada as recorder. The jobs are different, so we must remember who occupies each place. We call a choice in which the positions matter an ordered choice, or a permutation.

The team shown below the jobs ignores those job labels. It still contains the same two people after a swap. A choice that records only which people were chosen is a combination. We will count the job assignments first, then use that count to find the number of teams.

02Why does multiplication count the choices?

We could write down every job assignment, but it is easy to miss one. Let us keep the speaker fixed while we list the recorders. If Ada speaks, Ben, Cleo or Dan can record. That gives three assignments with Ada as speaker.

Each row below keeps one speaker on the left. A line leads to each allowed recorder on the right. A complete path therefore means one speaker and one recorder. Use Next step to open a row at a time; click a path to read its two jobs.

There are four rows, and every row contains three assignments. The rows cannot overlap: an assignment with Ada speaking is not an assignment with Ben speaking. Every possible assignment belongs to one of these rows, because its speaker must be one of the four friends. So we have four separate groups of three, which is what $4\times3$ counts.

The second choice depends on the first: we cannot use that person again. Yet there are three choices every time, whichever speaker we selected. That equal number is why multiplication works here. If an extra rule allowed different numbers of recorders in different rows, we would add those row counts instead.

03Give everybody a place

Keep our four friends, but now arrange all four in a line. There are four choices for the first place. After choosing that person, three remain for the second. Then two remain, and finally one. The same branching argument gives $4\times3\times2\times1=24$ complete lines.

We need a short name for this descending product, because it appears whenever every different person gets a place. We write $4!$, read four factorial, for $4\times3\times2\times1$. The exclamation mark is part of the mathematical notation; it does not mean to add or repeat the number four.

Below, $n$ names the number of people. One example line fills from left to right. Under each place, the factor records how many choices were available there, not which person we happened to put there. The product counts all possible lines; the displayed line is only one of them.

For any positive whole number $n$, the choices are $n$, then $n-1$, and so on down to $1$. Their product is called $n!$. Each complete line follows exactly one chain of choices, so no line is counted twice or left out.

04Fill only some of the places

Return to the speaker and recorder. We had four people but only two jobs, so we stopped after $4\times3$. Multiplying by $2\times1$ as well would arrange the two people who did not get jobs. We did not ask for that extra arrangement.

Now let $n$ be the number of available people, and $r$ the number of places to fill. We require whole numbers with $0\le r\le n$. The symbol $P(n,r)$ names the number of ordered choices. For four people and two jobs, it is $P(4,2)=4\times3=12$.

For $r>0$, the first place allows $n$ choices. The second allows $n-1$. Before the last of the $r$ places, we have used $r-1$ people, so the number remaining is $n-(r-1)=n-r+1$. We multiply these $r$ choice counts, using the same equal-branch argument as the two-job tree.

How can factorials shorten this expression? For the original example, $4!=4\times3\times2\times1$. The factors we want are $4\times3$. The unwanted tail is $2\times1=2!$. Dividing by that entire tail cancels it, leaving exactly the two factors we need.

Change $n$ or $r$, then step through the placements and cancellation. To keep the construction readable, this display fills at most three places; the argument works for every allowed $r$.

The same split works for general $n$ and $r$. After the $r$ wanted factors, the remaining tail starts at $n-r$ and ends at $1$: it is $(n-r)!$. Since a factorial is never zero, we may divide by it. This gives the factorial form below. When $r=0$, we keep no factors; the count is one empty choice.

05The same team has several orders

We can now count the teams. A team of Ada and Ben appears twice in the job list: Ada then Ben, and Ben then Ada. We are no longer assigning jobs, so those two orders must become one team. Every two-person team has these two orders; none has more or fewer.

The 12 job assignments therefore form six pairs. We divide by the number of orders of each same team, not by the number of people available. Here that number is $2!=2\times1=2$, so the team count is $12\div2=6$.

Watch the orders join their teams below. Letters keep the same person throughout; an arrow records order, while braces record only the members. Select a team to follow its orders. Then try three people per team: each fixed team has $3\times2\times1=6$ orders, because we are arranging its three members in three places.

This display uses up to five people and three selected members, so every order can remain visible. Changing either number restarts the grouping.

This explains the general division. First count all ordered selections of $r$ people from $n$: there are $P(n,r)$. Now keep the members of one selected group fixed. Its $r$ different members can be arranged in $r!$ orders, by the factorial argument. Every ordered selection has exactly one set of members, so it belongs to exactly one group. All groups contain the same number of orders, namely $r!$.

Let $C(n,r)$ name the number of groups. Group count multiplied by orders per group gives the whole ordered count: $C(n,r)\times r!=P(n,r)$. Divide both sides by $r!$. Then substitute the formula we just derived for $P(n,r)$. Dividing by $(n-r)!$ and then by $r!$ means dividing by their product.

You may also see $\binom{n}{r}$, read n choose r, for this same count. It is another notation for $C(n,r)$, not a new method. The important question remains: would swapping the selected people change what we want to record?

06Check the ends of the rule

A formula should agree with the meaning of the task. Let us check cases where we can count without it. Here we have four different people. Choosing nobody gives one empty result. Choosing everybody gives one team, but many different lines.

These formulas count different objects, without reuse. For example, a two-digit code may repeat the same digit, so its second place does not lose one choice. That is a different counting rule. Also, choosing five different people from only four is impossible: it gives zero results, and lies outside our stated range $0\le r\le n$.

07Decide what one result means

For each problem, decide whether the same selected people in a different order make a new result. Then write the choice counts before using factorials. Open an answer after trying; the explanation keeps the meaning of each factor visible.

The formulas came from two operations: multiply the choices at successive places, then, if positions do not matter, divide by the orders of each same group. Before choosing a formula, keep asking what counts as one different result.