Permutations and combinations are fundamental concepts in combinatorics, dealing with the arrangement and selection of objects from a set. Factorials Before diving into permutations and combinations, it's essential to understand factorials. The factorial of a non-negative integer $n$, denoted by $n!$, is the product of all positive integers less than or equal to $n$. $$n! = n \times (n-1) \times (n-2) \times \dots \times 3 \times 2 \times 1$$ By definition, $0! = 1$. Example: $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ Permutations Permutations refer to the arrangement of objects where the order matters. If you change the order of the objects, it's considered a different permutation. 1. Permutations of $n$ distinct objects taken $r$ at a time The number of permutations of $n$ distinct objects taken $r$ at a time is given by the formula: $$P(n, r) = \frac{n!}{(n-r)!}$$ Example 1: Arranging a subset How many ways can you arrange 3 different books on a shelf from a selection of 5 different books? Here, $n=5$ (total books) and $r=3$ (books to arrange). $$P(5, 3) = \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{5 \times 4 \times 3 \times 2 \times 1}{2 \times 1} = 5 \times 4 \times 3 = 60$$ There are 60 ways to arrange the books. 2. Permutations of $n$ distinct objects taken $n$ at a time This is a special case where $r=n$. The formula simplifies to: $$P(n, n) = \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n!$$ Example 2: Arranging all objects How many different ways can the letters of the word "MATH" be arranged? Here, $n=4$ (total letters) and $r=4$ (all letters are used). $$P(4, 4) = 4! = 4 \times 3 \times 2 \times 1 = 24$$ There are 24 different arrangements. 3. Permutations with Repetition (Identical Objects) If there are $n$ objects where $n_1$ are of one type, $n_2$ are of a second type, ..., $n_k$ are of a $k$-th type, and $n_1 + n_2 + \dots + n_k = n$, then the number of distinct permutations is: $$\frac{n!}{n_1! n_2! \dots n_k!}$$ Example 3: Arranging letters with repetition How many distinct arrangements can be made from the letters of the word "MISSISSIPPI"? Here, $n=11$ (total letters). M: 1 ($n_1=1$) I: 4 ($n_2=4$) S: 4 ($n_3=4$) P: 2 ($n_4=2$) Number of distinct arrangements = $\frac{11!}{1! 4! 4! 2!} = \frac{39,916,800}{1 \times 24 \times 24 \times 2} = \frac{39,916,800}{1152} = 34,650$ There are 34,650 distinct arrangements. Combinations Combinations refer to the selection of objects where the order does not matter. If you select a group of objects, changing the order in which you picked them does not create a new combination. 1. Combinations of $n$ distinct objects taken $r$ at a time The number of combinations of $n$ distinct objects taken $r$ at a time is given by the formula: $$C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$ Note that $C(n, r) = \frac{P(n, r)}{r!}$. This shows that for every $r!$ permutations, there is only 1 combination. Example 4: Selecting a committee A committee of 3 people is to be chosen from a group of 7 people. How many different committees can be formed? Here, $n=7$ (total people) and $r=3$ (people to choose). The order of selection does not matter for a committee. $$C(7, 3) = \frac{7!}{3!(7-3)!} = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1)(4 \times 3 \times 2 \times 1)} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 7 \times 5 = 35$$ There are 35 different committees that can be formed. Example 5: Selecting items from a menu A student needs to choose 2 subjects from a list of 4 optional subjects. How many ways can the student choose the subjects? Here, $n=4$ (total subjects) and $r=2$ (subjects to choose). The order of choosing subjects does not matter. $$C(4, 2) = \frac{4!}{2!(4-2)!} = \frac{4!}{2!2!} = \frac{4 \times 3 \times 2 \times 1}{(2 \times 1)(2 \times 1)} = \frac{12}{2} = 6$$ There are 6 ways to choose the subjects. Key Difference: Order Matters vs. Order Does Not Matter Permutations: Use when the order or arrangement* of the selected items is important (e.g., arranging books, forming a password, assigning positions). Combinations: Use when only the selection or group* of items is important, and their order does not change the outcome (e.g., choosing a committee, selecting lottery numbers, picking cards).