Summary

This chapter developed the basic tools of combinatorics used throughout the rest of the course.

• The Fundamental Principle of Counting: if one event can happen in $m$ ways and, independently, a second event can happen in $n$ ways, the two together can happen in $m \times n$ ways (multiplication for combined stages; addition for mutually exclusive alternatives).
• Factorial notation: $n! = n(n-1)(n-2)\cdots 2 \cdot 1$, with $0! = 1$ by convention, and the recurrence $n! = n \times (n-1)!$ used to simplify factorial ratios.
• A permutation is an ordered arrangement of $r$ objects out of $n$ distinct objects, derived from the Fundamental Principle of Counting as $^{n}P_{r} = n(n-1)\cdots(n-r+1) = \dfrac{n!}{(n-r)!}$.
• Variations on permutations: with repetition allowed, $n^{r}$; for objects not all distinct, $\dfrac{n!}{p_1!\,p_2!\cdots p_k!}$; and restricted arrangements handled by fixing positions, blocking objects together, or subtracting the unwanted "together" case from the total. …