Permutations & Combinations

Cheatsheet Content

### Fundamental Principles of Counting - **Multiplication 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. - **Addition Principle:** If an event can occur in $m$ ways and another event can occur in $n$ ways, and both cannot occur simultaneously, then either event can occur in $m + n$ ways. ### Factorial - **Definition:** For a natural number $n$, $n! = n \times (n-1) \times \dots \times 2 \times 1$. - **Special Cases:** $0! = 1$ and $1! = 1$. ### Permutations - **Definition:** An arrangement of a set of objects in a definite order. The order matters. - **Permutations of $n$ distinct objects taken $r$ at a time:** $$P(n, r) = {}^n P_r = \frac{n!}{(n-r)!}$$ where $0 \le r \le n$. - **Permutations of $n$ distinct objects taken all at a time:** $P(n, n) = n!$ - **Permutations with Repetition:** - The number of permutations of $n$ objects where $p_1$ objects are of one kind, $p_2$ are of second kind, ..., $p_k$ are of $k^{th}$ kind is: $$\frac{n!}{p_1! p_2! \dots p_k!}$$ - **Circular Permutations:** - For $n$ distinct objects arranged in a circle: $(n-1)!$ - If clockwise and anti-clockwise arrangements are considered the same (e.g., necklaces, garlands): $\frac{(n-1)!}{2}$ ### Combinations - **Definition:** A selection of objects from a set where the order of selection does not matter. - **Combinations of $n$ distinct objects taken $r$ at a time:** $$C(n, r) = {}^n C_r = \frac{n!}{r!(n-r)!}$$ where $0 \le r \le n$. - **Properties of Combinations:** - ${}^n C_r = {}^n C_{n-r}$ - ${}^n C_0 = 1$ and ${}^n C_n = 1$ - ${}^n C_1 = n$ - ${}^n C_r + {}^n C_{r-1} = {}^{n+1} C_r$ (Pascal's Identity) - If ${}^n C_x = {}^n C_y$, then either $x=y$ or $x+y=n$. - **Combinations with Repetition (Stars and Bars):** - The number of ways to choose $r$ objects from $n$ types of objects with repetition allowed is: $${}^{n+r-1} C_r$$ ### Important Results & Formulas - **Number of arrangements of $n$ objects such that $k$ particular objects are always together:** Treat the $k$ objects as one block. Arrange $(n-k+1)$ objects. Then arrange the $k$ objects among themselves. Result: $(n-k+1)! \times k!$ - **Number of arrangements of $n$ objects such that $k$ particular objects are never together:** Total arrangements - Arrangements where $k$ objects are always together. Result: $n! - [(n-k+1)! \times k!]$ - **Number of ways to select at least one item from $n$ distinct items:** $2^n - 1$ - **Number of ways to select at least one item from $n$ items where $p_1$ are of one kind, $p_2$ of second, ..., $p_k$ of $k^{th}$ kind:** $(p_1+1)(p_2+1)\dots(p_k+1) - 1$ - **Distribution of $n$ distinct items into $r$ distinct boxes:** $r^n$ (each item has $r$ choices) - **Distribution of $n$ identical items into $r$ distinct boxes (each box can be empty):** ${}^{n+r-1} C_{r-1}$