Unit 24 · Permutations and Combinations
Count outcomes with the addition and multiplication principles, and use the factorial $n!$ with its recurrence relation $n! = n\,(n-1)!$.
Many problems ask "in how many different ways can ...". Listing every way is hopeless when there are thousands, so we use a few rules. These are the fundamental counting principles, and everything in permutations and combinations is built on them.
Suppose an outfit is one shirt and one pair of trousers. With $3$ shirts and $4$ pairs of trousers, each shirt can go with $4$ pairs of trousers, so there are $3 \times 4 = 12$ outfits.
Multiplication principle. If a task is done in several steps, and step 1 can be done in $m_1$ ways, step 2 in $m_2$ ways (whichever way step 1 was done), and so on up to step $k$ in $m_k$ ways, then the whole task can be done in $$m_1 \times m_2 \times \cdots \times m_k$$ ways. Use it when the steps are all done ("and").
Suppose you can go from town $A$ to town $B$ by $3$ different buses or by $2$ different trains. You use one bus or one train, never both, so there are $3 + 2 = 5$ ways.
Addition principle. If a task can be done in $m$ ways, or in $n$ other ways, and no way is counted in both, then there are $m + n$ ways. Use it when the cases are alternatives ("or") that cannot happen together.
Example: How many $3$-digit numbers are there (from $100$ to $999$)? The hundreds digit can be any of $1,\dots,9$ ($9$ ways, since $0$ is not allowed first). The tens digit can be any of $0,\dots,9$ ($10$ ways) and so can the units digit ($10$ ways). By the multiplication principle there are $9 \times 10 \times 10 = 900$ numbers.
Example: How many $2$-digit numbers have both digits odd, or both digits even? Both odd: $5 \times 5 = 25$ numbers. Both even: the tens digit is $2,4,6,8$ ($4$ ways) and the units digit is $0,2,4,6,8$ ($5$ ways), so $20$ numbers. No number is in both lists, so by the addition principle there are $25 + 20 = 45$.
Arranging objects in a line leads to products of consecutive integers. For $n \in \mathbb{Z}^+$ the factorial of $n$ is $$n! = n(n-1)(n-2)\cdots 3 \times 2 \times 1.$$ So $1! = 1$, $2! = 2$, $3! = 6$, $4! = 24$, $5! = 120$, $6! = 720$, $7! = 5040$. We also define $0! = 1$.
The recurrence relation is $$n! = n,(n-1)! \qquad (n \ge 1).$$ Putting $n = 1$ gives $1! = 1 \times 0!$, which is why $0! = 1$ is the sensible definition. A useful consequence is that the long common part cancels: $$\frac{n!}{(n-3)!} = n(n-1)(n-2), \qquad \frac{10!}{7!} = 10 \times 9 \times 8 = 720.$$ Never compute $10!$ and $7!$ in full; cancel first.
Example: Evaluate $\dfrac{10!}{7!,3!}$. Write $10! = 10 \times 9 \times 8 \times 7!$, so $\dfrac{10!}{7!,3!} = \dfrac{10 \times 9 \times 8}{3 \times 2 \times 1} = \dfrac{720}{6} = 120$.
Example: Show that $n! + (n+1)! = n!,(n+2)$. Use $(n+1)! = (n+1),n!$. Then $n! + (n+1)! = n!,[1 + (n+1)] = n!,(n+2)$.
Exam tip: In factorial equations and proofs, factor out the smallest factorial present, as in $n!,(n+2)$ above, instead of expanding. Always keep $n \in \mathbb{Z}^+$ (or $n \ge 0$) in mind and reject any solution that makes a factorial's argument negative.
When one position has a condition, fill it first, then fill the free positions.
Example: How many $4$-digit numbers can be made from the digits $1,2,3,4,5,6$ if no digit is repeated and the number is even? Fill the units digit first: $2, 4$ or $6$ gives $3$ ways. Then the thousands digit has $5$ choices left, the hundreds $4$, and the tens $3$. Total $3 \times 5 \times 4 \times 3 = 180$.