Permutations and Combinations

Cheatsheet Content

1. Fundamental Counting Principle If an event can occur in $m$ ways and another independent event can occur in $n$ ways, then both events can occur in $m \times n$ ways. Example: Choosing a shirt (3 options) and pants (2 options) gives $3 \times 2 = 6$ outfits. 2. Factorial The product of all positive integers less than or equal to a given positive integer $n$. Notation: $n!$ Formula: $n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1$ Special Case: $0! = 1$ Example: $4! = 4 \times 3 \times 2 \times 1 = 24$ 3. Permutations (Order Matters) Arrangements of objects where the order of selection is important. 3.1. Permutations of $n$ distinct objects taken $r$ at a time Notation: $P(n, r)$, $_nP_r$, or $P^n_r$ Formula: $P(n, r) = \frac{n!}{(n-r)!}$ Example: Arranging 3 out of 5 distinct books on a shelf: $P(5, 3) = \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{120}{2} = 60$ 3.2. Permutations of $n$ distinct objects (all at once) Formula: $P(n, n) = n!$ Example: Arranging 4 people in a line: $4! = 24$ 3.3. Permutations with Repetition Arrangement of $n$ objects where there are $n_1$ identical objects of type 1, $n_2$ identical objects of type 2, ..., $n_k$ identical objects of type $k$. Formula: $\frac{n!}{n_1! n_2! \dots n_k!}$ (where $n = n_1 + n_2 + \dots + n_k$) Example: Arranging the letters of "MISSISSIPPI": $n=11$ (total letters) M: $n_1=1$ I: $n_2=4$ S: $n_3=4$ P: $n_4=2$ Number of arrangements: $\frac{11!}{1!4!4!2!} = \frac{39,916,800}{1 \times 24 \times 24 \times 2} = 34,650$ 3.4. Circular Permutations Arranging $n$ distinct objects in a circle: $(n-1)!$ Arranging $n$ distinct objects in a circle where clockwise and counter-clockwise arrangements are considered the same (e.g., beads on a necklace): $\frac{(n-1)!}{2}$ Example: Arranging 5 people around a circular table: $(5-1)! = 4! = 24$ 4. Combinations (Order Does Not Matter) Selections of objects where the order of selection is not important. 4.1. Combinations of $n$ distinct objects taken $r$ at a time Notation: $C(n, r)$, $_nC_r$, $\binom{n}{r}$ Formula: $C(n, r) = \frac{n!}{r!(n-r)!}$ or $C(n, r) = \frac{P(n, r)}{r!}$ Properties: $C(n, r) = C(n, n-r)$ $C(n, 0) = 1$ $C(n, n) = 1$ Example: Choosing 2 students from a group of 5 for a committee: $C(5, 2) = \frac{5!}{2!(5-2)!} = \frac{5!}{2!3!} = \frac{120}{2 \times 6} = \frac{120}{12} = 10$ 4.2. Combinations with Repetition (Stars and Bars) Selecting $r$ items from $n$ types of items with repetition allowed. Formula: $C(n+r-1, r)$ or $C(n+r-1, n-1)$ Example: Choosing 3 scoops of ice cream from 5 available flavors (repetition allowed): $C(5+3-1, 3) = C(7, 3) = \frac{7!}{3!(7-3)!} = \frac{7!}{3!4!} = \frac{5040}{6 \times 24} = 35$ 5. Key Differences Summary Feature Permutations Combinations Order Matters (e.g., arrangements, sequences) Does not matter (e.g., selections, groups) Question Type "How many ways to arrange?", "How many different orderings?" "How many ways to choose?", "How many different groups?" Formula $P(n,r) = \frac{n!}{(n-r)!}$ $C(n,r) = \frac{n!}{r!(n-r)!}$ Result Generally larger number of possibilities Generally smaller number of possibilities