Permutations, arrangements and combinations

Five friends line up for a photo. How many different photos are possible? Now pick two of the five to carry the banner: how many choices? The first question cares about order, the second does not. This lesson gives you the formulas for both, and a simple test to know which one to use.

Permutations and factorials

There are $n$ choices for the first place, $n-1$ for the second, and so on: this is the multiplication rule from the counting rules.

Arrangements

Combinations

Each subset of $k$ objects can be ordered in $k!$ ways, so dividing the arrangements by $k!$ removes the order.

Two useful rules:

• Symmetry: $\binom nk=\binom n{n-k}$ (choosing who is in is the same as choosing who is out).
• Pascal's rule: $\binom nk+\binom n{k+1}=\binom{n+1}{k+1}$. For example $\binom{5}{2}+\binom{5}{3}=10+10=20=\binom{6}{3}$.

Problems with several groups

Conditions: together and apart

Key terms

Summary

• $n!$ counts the orderings of $n$ objects.
• $P(n, k)=\frac{n!}{(n-k)!}$ counts ordered choices; $\binom nk=\frac{n!}{k!(n-k)!}$ counts unordered choices.
• $\binom nk=\binom n{n-k}$ and $\binom nk+\binom n{k+1}=\binom{n+1}{k+1}$.
• Test: does swapping two chosen objects change the outcome?

Practice

Show solutions

1. $6!=720$.
2. $7\cdot6=42$.
3. $\frac{10\cdot9\cdot8}{3\cdot2\cdot1}=120$.
4. $\frac{n(n-1)}{2}=28$, so $n^2-n-56=0$ and $n=8$ (the negative root is rejected).
5. $\binom{7}{3}\binom{5}{2}=35\cdot10=350$.
6. Order matters: $P(7, 3)=7\cdot6\cdot5=210$.
7. Total $6!=720$. A and B together: $2\cdot5!=240$. Not together: $720-240=480$.
8. $4!=24$ words. With M first, the other $3$ letters can be ordered in $3!=6$ ways.
9. Pairs of vertices $\binom{10}2=45$ minus $10$ sides: $35$.
10. Triangles $\binom{8}{3}=56$; quadrilaterals $\binom{8}{4}=70$ (any $4$ points on a circle form a quadrilateral).