Permutations and Combinations

Four distinct objects $A$, $B$, $C$, $D$ arranged in a row: $4!=24$. That number is right.

Now three questions that still feel like "arranging four things", each of which the reflex answers $24$.

Three different answers from one starting number, and nothing was wrong with the $24$. What differed was how many times each real object appeared inside it: four, two and six.

Build the object one decision at a time, then divide out every way you counted the same object more than once.

That is the whole chapter. The building gives the multiplication principle and every permutation count. The dividing gives combinations, repeated letters and circular arrangements, which are the same correction applied to three different overcounts.

$\text{answer}=\frac{\text{count with everything treated as distinct and ordered}}{\text{number of times each real object was counted}}$

You do not choose between five similar formulas. You build, then correct.

1. The Fundamental Principle of Counting

Multiplication principle. If one decision has $m$ outcomes and an independent second has $n$, the pair has $mn$.

Addition principle. If the cases are mutually exclusive, add their counts.

Trap. The multiplication principle needs the second count to be the same whichever way the first went. If the first choice changes how many options the second has, split into cases and add.

Start with the most constrained decision. A slot that forbids something must be filled first, or you will not know how many options the later slots have.

Illustration 1

Using the digits $0,1,2,3,4,5$ without repetition, how many three-digit numbers can be formed, and how many of those are even?

For any three-digit number the leading digit cannot be $0$, which is the constraint, so fill that slot first.

$5\times 5\times 4=100$

Five choices lead (everything but $0$), then five remain for the second slot ($0$ is available again), then four.

For the even ones there are now two constrained slots, the first and the last, and they interact. Split into cases.

Last digit $0$: the leading slot is no longer restricted, since $0$ is spent. That gives $5\times 4=20$.

Last digit $2$ or $4$: two ways to choose it, then the leading digit avoids both $0$ and that digit, leaving $4$, then $4$ remain.

$2\times 4\times 4=32$

$\text{total}=20+32=52$

Multiplying blindly would give $5\times 4\times 3=60$, counting numbers like $032$. The cases were needed because whether $0$ is still available in the leading slot depends on what the last slot took.

2. Permutations: Arrangements Without Repetition

Permutation. An arrangement, in which order matters.

${}^n{P}_r=\frac{n!}{(n-r)!}=n(n-1)\cdots (n-r+1)$

That is the multiplication principle with the options shrinking by one each time: $n$ for the first slot, $n-1$ for the next, down to $n-r+1$ for the last.

With repetition allowed, nothing shrinks and the count is $n^r$.

3. Combinations: Dividing Out the Order

Combination. A selection, in which order does not matter.

Build the ordered version, then divide by the number of orderings of each selection.

${}^n{C}_r=\frac{{}^n{P}_r}{r!}=\frac{n!}{r!(n-r)!}$

Illustration 2

Prove Pascal's identity ${}^n{C}_r={}^{n-1}{C}_{r-1}+{}^{n-1}{C}_r$ without any algebra.

Single out one particular object, say the first. Every selection of $r$ objects either contains it or does not, and never both, so the two cases are exclusive and their counts add.

It is in. The remaining $r-1$ places are filled from the other $n-1$ objects: ${}^{n-1}{C}_{r-1}$ ways.

It is out. All $r$ places are filled from the other $n-1$ objects: ${}^{n-1}{C}_r$ ways.

${}^n{C}_r={}^{n-1}{C}_{r-1}+{}^{n-1}{C}_r$

The factorial proof takes half a page of common denominators and tells you nothing. This one takes two lines and explains why Pascal's triangle has each entry as the sum of the two above it.

Illustration 3

If ${}^{20}{C}_{3r}={}^{20}{C}_{r+4}$, find all possible values of $r$.

The instinct is to equate the lower indices and stop. That misses half the answer, because ${}^n{C}_r={}^n{C}_{n-r}$ means two different lower indices can give the same value.

Case 1, the indices are equal.

$3r=r+4\Rightarrow r=2$

Case 2, the indices are complementary.

$3r+(r+4)=20\Rightarrow 4r=16\Rightarrow r=4$

Both must be checked against $0\le \text{index}\le 20$, and both survive: $r=2$ gives ${}^{20}{C}_6={}^{20}{C}_6$, and $r=4$ gives ${}^{20}{C}_{12}={}^{20}{C}_8$.

$r=2\text{ or }4$

The symmetry that makes this question possible is the same one that makes ${}^{20}{C}_{17}$ easy: rewrite it as ${}^{20}{C}_3$ and the arithmetic collapses from seventeen factors to three.

4. Permutations with Repeated Objects

Identical objects create the second kind of overcount: swapping two identical letters produces a different-looking arrangement that is really the same one.

$\frac{n!}{p!q!r!\cdots }$

where $p,q,r$ are the counts of each repeated object.

Illustration 4

How many arrangements are there of the letters of $\text{BALLOON}$, and in how many of them are the two L's together?

Seven letters, with L twice and O twice.

$\frac{7!}{2!2!}=\frac{5040}{4}=1260$

For the L's together, glue them into one block. That block plus $\text{B},\text{A},\text{O},\text{O},\text{N}$ makes six items to arrange, still with O twice.

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

No extra factor for arranging inside the block, because the two L's are identical: swapping them within the block changes nothing. Had the block been two different letters, the answer would have been doubled.

As a check, $360/1260=2/7$, and that is exactly the chance that two specified positions out of seven are adjacent in the sense required, so the fraction is plausible rather than merely arithmetic.

5. Circular Permutations

Around a circle there is no first seat. Fixing one person removes the rotational overcount, which is the third kind.

$\text{circular arrangements of }n\text{ objects}=(n-1)!$

Illustration 5

How many different garlands can be made from $6$ distinct flowers?

Round a circle, the rotational overcount gives $(6-1)!=120$.

But a garland can be picked up and turned over, and the reversed arrangement is the same physical garland. That is a second overcount, of exactly $2$.

$\frac{(6-1)!}{2}=\frac{120}{2}=60$

The same correction applies to necklaces and to any circular object with no fixed face. It does not apply to people at a round table, because a table cannot be flipped and the person on your left stays on your left.

Trap. Decide first whether reflections are genuinely indistinguishable. Garland and necklace mean divide by two; seating and round-table questions do not.

6. Restrictions and the Standard Devices

Objects that must be together

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

Objects that must not be together

Arrange the others first, then drop the restricted ones into the gaps. With $m$ objects in a row there are $m+1$ gaps, including the two ends.

At least and at most

Count the complement when the phrase is "at least one". The opposite of "at least one" is "none", which is a single easy count.

$\text{at least one}=\text{everything}-\text{none}$

For "at least two of five", the complement is two cases rather than one, so direct case-counting is usually faster. Compare the number of cases each way before committing.

Illustration 6

From $6$ men and $4$ women, a committee of $5$ is to contain at least $3$ men. Count it both ways and see which is shorter.

Directly, by number of men.

${}^6{C}_3{}^4{C}_2+{}^6{C}_4{}^4{C}_1+{}^6{C}_5{}^4{C}_0=20(6)+15(4)+6(1)=186$

By complement, subtracting the committees with at most $2$ men.

${}^{10}{C}_5=252,{}^6{C}_2{}^4{C}_3+{}^6{C}_1{}^4{C}_4=15(4)+6(1)=66$

$252-66=186$

The committee with no men at all would need five women and only four exist, so that case contributes nothing and the complement needs two terms against the direct route's three.

$\text{count the cases on each side first; take the shorter list}$

Agreement between the two routes is also the best available check, since an arithmetic slip is very unlikely to survive both.

Illustration 7

In how many ways can the letters of $\text{SUCCESS}$ be arranged so that no two S's are adjacent?

Seven letters: $\text{S}$ three times, $\text{C}$ twice, plus $\text{U}$ and $\text{E}$.

Gap method. Arrange the four non-S letters first, remembering the repeated C.

$\frac{4!}{2!}=12$

Those four letters create $5$ gaps. Choosing any $3$ of them for the S's guarantees a letter stands between each pair.

${}^5{C}_3=10$

No factor for arranging the S's among themselves, since they are identical.

$12\times 10=120$

The two overcount corrections appear in the same line and do different jobs: $2!$ removes the duplicate C's, and using ${}^5{C}_3$ rather than ${}^5{P}_3$ removes the ordering of identical S's.

Illustration 8

A basket holds $3$ identical apples, $4$ identical oranges and $2$ identical pears. In how many ways can a non-empty selection be made?

Because the fruits of each kind are identical, a selection is entirely described by how many of each kind it contains, not which ones.

$\text{apples: }0,1,2,3(4\text{ ways})\text{oranges: }5\text{ ways}\text{pears: }3\text{ ways}$

$(3+1)(4+1)(2+1)=60$

That count includes taking nothing at all, so remove it.

$60-1=59$

Contrast with $9$ distinct fruits, where each is independently in or out and the answer would be $2^9-1=511$. Identical objects collapse the choices from "which" to "how many", and that is the entire difference.

7. Selections from Groups and Integer Solutions

For selections drawn from several groups, choose from each group and multiply, then add over the allowed splits.

The number of non-negative integer solutions of $x_1+x_2+\cdots +x_r=n$ is a stars-and-bars count.

${}^{n+r-1}{C}_{r-1}$

Illustration 9

Find the number of positive integer solutions of $x+y+z=12$, and compare with the non-negative count.

Positive means every variable is at least $1$, so the bars must not share a gap and none may sit at an end. Twelve stars leave $11$ gaps, and two bars occupy two of them.

${}^{11}{C}_2=55$

For non-negative solutions, zeros are allowed, so bars may sit together or at the ends. Substituting $x=a+1$ and so on converts one problem to the other.

${}^{12+3-1}{C}_{3-1}={}^{14}{C}_2=91$

$91-55=36$

Those $36$ are exactly the solutions with at least one zero, which you can verify: $3\times {}^{13}{C}_1-3=39-3=36$ after correcting for the three double-zero cases counted twice.

Trap. Read whether the variables may be zero before choosing the formula. The two answers here differ by nearly a factor of two.

8. Dividing Objects into Groups

Dividing $n$ objects into groups of stated sizes uses the repeated-object formula, with one extra correction that catches almost everyone.

$\text{groups of sizes }p,q,r:\frac{n!}{p!q!r!}$

If some groups have equal size and are unlabelled, divide again by the factorial of the number of equal groups, because swapping two identical-sized unlabelled groups produces the same division.

Illustration 10

Divide $9$ people into groups of $4$, $3$ and $2$. Then divide $6$ people into three groups of $2$. Explain why only the second needs the extra division.

$\frac{9!}{4!3!2!}=\frac{362880}{24\times 6\times 2}=1260$

No further correction. The groups have different sizes, so they are already distinguishable, and swapping them would change which group is which.

$\frac{6!}{2!2!2!}=\frac{720}{8}=90,\text{then }\frac{90}{3!}=15$

Here the three groups are indistinguishable. Any one division has been counted $3!=6$ times, once for each way of labelling the three pairs as "first", "second", "third".

If the question had named the groups, calling them rooms or teams $A$, $B$, $C$, the answer would be $90$, since the labels make the groups distinguishable again.

9. Two Standard Applications

Counting divisors

Write $N$ in prime factorisation. Each prime's exponent is chosen independently, from $0$ up to its maximum.

$N=p^a{q}^b{r}^c\Rightarrow \text{number of divisors}=(a+1)(b+1)(c+1)$

Illustration 11

For $N=2^4\cdot 3^3\cdot 5^2$, how many divisors are there in total, and how many are perfect squares?

$(4+1)(3+1)(2+1)=60$

A divisor is a perfect square exactly when every exponent in it is even, so count the even choices for each prime separately.

$2^0,2^2,2^4(3)3^0,3^2(2)5^0,5^2(2)$

$3\times 2\times 2=12$

The structure never changed; only the menu at each prime shrank. The same method counts divisors that are perfect cubes, or divisible by $6$, by restricting the exponent lists accordingly.

Points, lines and triangles

Every line needs two points and every triangle needs three, so the counts are combinations, with a correction wherever points are collinear.

Illustration 12

Ten points lie in a plane, of which exactly four are collinear. How many lines and how many triangles do they determine?

Start from the unrestricted counts, then repair the damage the collinear four cause.

${}^{10}{C}_2=45,{}^{10}{C}_3=120$

Lines. The four collinear points would have given ${}^4{C}_2=6$ separate lines, but they all lie on one line.

$45-6+1=40$

Triangles. Any three of the collinear four give no triangle at all, so those selections are simply deleted.

$120-{}^4{C}_3=120-4=116$

Note the difference between the two repairs. Lines lost six and regained one, because a line still exists; triangles lost four and regained nothing, because a degenerate triangle is not a triangle.

The diagonal formula comes from the same idea: a polygon's ${}^n{C}_2$ point pairs include the $n$ sides, which are not diagonals, so a decagon has $45-10=35$ diagonals.

Rank of a word

List all arrangements in dictionary order and find the position of a given word. Work letter by letter: at each position, count the arrangements that start with a smaller letter, then move on.

Illustration 13

Find the rank of $\text{CAB}$ among the arrangements of $\text{A},\text{B},\text{C}$.

Position 1. Words beginning with a letter before C: that is A or B, two choices, each followed by $2!=2$ arrangements.

$2\times 2!=4$

Position 2. Among the words beginning with C, those with a second letter before A: none, since A is smallest.

$0\times 1!=0$

Position 3. Nothing is left to choose.

$\text{rank}=4+0+0+1=5$

Check by listing: ABC, ACB, BAC, BCA, CAB, CBA. The final $+1$ is what turns "how many come before it" into "what position is it".

Summary

Build the object one decision at a time, then divide out every way you counted the same object twice.

Three overcounts, one correction: ordering gives $r!$, identical objects give $p!q!\cdots$, rotation gives $n$.

Multiply for independent decisions, add for exclusive cases, and fill the most constrained slot first. If the second count depends on the first choice, split into cases.

${}^n{P}_r=n!/(n-r)!$ with order, $n^r$ with repetition allowed, and ${}^n{C}_r={}^n{P}_r/r!$ without order.

Pascal's identity is one sentence: the singled-out object is either in or out.

Repeated letters divide by the factorial of each repeat count. Gluing objects into a block needs an internal factor only if the glued objects are distinct.

Circular arrangements are $(n-1)!$; garlands and necklaces divide again by $2$ for flipping, tables do not.

Together means glue; not together means arrange the rest and use the $m+1$ gaps; at least one usually means take the complement.

Identical objects turn "which" into "how many", so selections come to $(p+1)(q+1)(r+1)$, less one for the empty choice.

Non-negative solutions of a sum equation are ${}^{n+r-1}{C}_{r-1}$; positive solutions are ${}^{n-1}{C}_{r-1}$, and the wording decides which.

Groups of unequal size need no extra division; equal-sized unlabelled groups need division by the factorial of how many are equal.

Two lower indices give the same combination when they are equal or complementary, so identity equations have two cases.

Lines and triangles from points are ${}^n{C}_2$ and ${}^n{C}_3$; collinear points cost a line six and give one back, and cost a triangle its whole selection.

Divisor counts multiply $(a+1)$ over the prime exponents, and restricting the exponent menus counts special divisors such as perfect squares.

Rank of a word is a positional count of everything alphabetically before it, plus one.