Permutations and combinations

5.2 Permutations and combinations

Permutations and combinations

Arrangements in a line

$n$ different objects can be arranged in $n!$ ways. Picking and arranging $r$ of them gives ${}^n\mathrm{P}_r$ ways.

Repeated objects

If some objects are the same, divide by the factorial of each repeat, since swapping them changes nothing.

There are 8 letters, with E three times and S twice:

$\frac{8!}{3!\,2!} = \frac{40320}{12} = 3360$

Things that must be together

Glue the group into a single block, arrange the blocks, then arrange inside the block.

Treat the pair as one, giving 5 objects: $5!$ ways. The pair can swap: $2!$ ways.

$5! \times 2! = 240$

Treat EEE as one block, giving 6 objects with S repeated. The block has no internal order, since the Es are the same.

$\frac{6!}{2!} = 360$

Things that must be apart

There are two methods.

Total minus together, which works for a pair:

$6! - 240 = 480$

Filling the gaps, which works for several items that must be apart. Arrange the others first, then place the separated items in the gaps.

Arrange the boys: $4!$ ways. This leaves 5 gaps, counting the two ends, and the 3 girls go into different gaps: ${}^5\mathrm{P}_3 = 60$ ways.

$24 \times 60 = 1440$

Items in fixed positions

Fill any restricted positions first.

The two Ss are placed. The other 6 letters include EEE, so $\dfrac{6!}{3!} = 120$.

Selections

${}^4\mathrm{C}_2 \times {}^6\mathrm{C}_3 = 6 \times 20 = 120$

Multiply when you are making one choice and then another. Add when listing separate cases.

"At least" and "at most"

It is quicker to subtract the all-men committees from the total:

${}^{10}\mathrm{C}_5 - {}^6\mathrm{C}_5 = 252 - 6 = 246$

List the cases: 3 men and 2 women, or 4 men and 1 woman.

${}^6\mathrm{C}_3{}^4\mathrm{C}_2 + {}^6\mathrm{C}_4{}^4\mathrm{C}_1 = 120 + 60 = 180$

People who must or must not be together in a selection

If two people must both be on the committee, include them and choose the rest from those left. If they refuse to serve together, take the total minus the selections with both.

With both: ${}^8\mathrm{C}_3 = 56$. So the number allowed is $252 - 56 = 196$.

Selections from repeated letters

If letters are repeated, split the cases by how many of the repeated letter you use.

The letters are N, E, E, E, D, L, S, S. List by the number of Es, and within each, the number of Ss, with the rest from N, D, L.

The total is 22.