Permutations and combinations

Permutations and combinations: what the words mean

Counting questions ask "in how many ways?". The first decision is always whether order matters.

• A permutation is an arrangement: the order matters. ABC and CAB are different arrangements of the same three letters.
• A combination is a selection: the order does not matter. Choosing Ali, Ben and Cara for a team is the same selection as choosing Cara, Ali and Ben.

Everything in this topic rests on the multiplication principle: if one choice can be made in $m$ ways and then, whatever happened, a second choice can be made in $n$ ways, the two together can be made in $mn$ ways. When a problem splits into separate cases that cannot happen together, you add the counts for the cases.

Factorials. $n!=n\times (n-1)\times \dots \times 2\times 1$, and $0!=1$. Factorials grow very fast: $10!=3628800$. Your calculator has an $x!$ key, and also keys for ${}^n{P}_r$ and ${}^n{C}_r$. Answers are exact whole numbers: never round them.

Arranging objects in a line

To arrange $n$ different objects in a line, fill the positions one at a time. The first position can take any of the $n$ objects, the second any of the $n-1$ left, and so on, down to 1 for the last. So there are
$$n\times (n-1)\times \dots \times 1=n!$$
arrangements. Five people can stand in a queue in $5!=120$ ways.

If only $r$ of the $n$ objects are placed in a line, stop after $r$ positions:
$${}^n{P}_r=n\times (n-1)\times \dots \times (n-r+1)=\frac{n!}{(n-r)!}$$
For example, the number of 4-digit codes using four different digits from 1 to 9 is ${}^9{P}_4=9\times 8\times 7\times 6=3024$.

When a position has a condition (the number must be even, so the last digit is restricted), fill the restricted position first, then fill the others from what is left.

Arrangements with repeated objects

If some of the objects are identical, $n!$ counts too many arrangements. Take the letters of NEEDLESS, the syllabus example. It has 8 letters: N, D, L, three Es and two Ss. If the three Es were labelled $E_1$, $E_2$, $E_3$, there would be $8!$ arrangements. But each real arrangement, such as NEEDLESS itself, appears $3!$ times in that list (once for each order of the labelled Es), and each of those appears $2!$ times for the Ss. So
$$\text{number of arrangements}=\frac{8!}{3!2!}=\frac{40320}{12}=3360.$$
In general, $n$ objects of which $p$ are alike, $q$ others are alike, and so on, can be arranged in $\frac{n!}{p!q!\dots }$ ways.

Always list the letters and count each repeat before you start: one missed repeat is the commonest way to lose every mark in the question.

Arrangements with restrictions

Objects that must be together. Treat them as a single block. Arrange the block with the other objects, then multiply by the number of ways to arrange the objects inside the block. Why multiply? For every arrangement of the blocks, each internal order gives a different line.

So if 8 people stand in a line and A and B must stand next to each other, arrange 7 items (the block [AB] and 6 others) in $7!$ ways, and the block itself in $2!$ ways: $2\times 7!=10080$.

Objects that must not be together. For two objects, it is quickest to subtract: arrangements with A and B apart $=8!-2\times 7!=40320-10080=30240$.

For several objects of which no two may be next to each other, use the gaps method. Arrange the other objects first, then place the restricted objects in the gaps between them and at the ends, at most one per gap. For example, 5 boys and 3 girls stand in a line with no two girls next to each other. Arrange the boys: $5!=120$. That leaves 6 gaps (including the two ends), so place the girls in 3 of them in order: ${}^6{P}_3=120$. Total $120\times 120=14400$. Subtracting "girls together" from the total would be wrong here: it removes only the cases where all three girls are together, but two girls next to each other is also forbidden.

Objects in particular positions (at the ends, in the middle): fill those positions first, then arrange the rest.

Two or more rows

The syllabus includes people sitting in two (or more) rows. Questions about objects arranged in a circle are not included.

Rows need no new formula: treat each seat as a position. If 9 people sit in 9 seats arranged as a front row of 4 and a back row of 5, there are still $9!$ ways, because each seat is a distinct place.

The care is needed with conditions. "Next to each other" means in the same row and in adjacent seats: a person at the end of the front row is not next to a person at the start of the back row. Count the possible pairs of adjacent seats in each row (a row of 4 seats has 3 adjacent pairs), and remember each pair can be filled in 2 orders.

When a condition says some people must sit in a particular row, place them first: choose their seats in order, then let everyone else fill the remaining seats.

Selections

The number of ways of selecting $r$ objects from $n$ different objects, when order does not matter, is
$${}^n{C}_r=\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\frac{n!}{r!(n-r)!}$$
Why the extra $r!$? There are ${}^n{P}_r$ ordered choices, and every selection of $r$ objects appears $r!$ times among them, once for each order. Notice that $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-r}\right)$: choosing 3 people to go is the same as choosing the 7 who stay.

Selections with conditions are handled by thinking in groups.

• Exactly $k$ from one group: choose those $k$ from that group and the rest from the others, and multiply. From 7 women and 5 men, a committee of 5 with exactly 3 women: $\left(\genfrac{}{}{0ex}{}{7}{3}\right)\left(\genfrac{}{}{0ex}{}{5}{2}\right)=35\times 10=350$.
• At least or at most: list the cases and add, or use the complement, "total minus the cases you do not want". For "at least one", the complement is nearly always quickest.
• Must include a particular person: put them in, then choose the rest from the others.
• Two people who refuse to serve together: total minus the selections containing both.

If you add cases, make sure they do not overlap and that none is missed.

Permutation or combination?

Ask: if I swap two of the chosen objects, do I get a different outcome?

• Yes (a different queue, a different number, a different seating): it is an arrangement, so use $n!$, ${}^n{P}_r$ or $\frac{n!}{p!q!}$.
• No (the same team, the same hand of cards, the same set of letters): it is a selection, so use $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$.

Some problems need both. "Choose 3 of the 8 runners for a relay team, then decide the running order" is $\left(\genfrac{}{}{0ex}{}{8}{3}\right)\times 3!={}^8{P}_3$.

Selections from objects that are not all different, such as choosing 4 letters from CALCULUS, cannot be done with a single $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, because choosing the first C or the second C gives the same selection. Split into cases by how many repeated letters are chosen, and count each case separately.

These counts also give probabilities when every arrangement or selection is equally likely: divide the number of favourable ones by the total number. You will use this in the next topic.