Permutations & Combinations

Cheatsheet Content

1. Fundamental Counting Principles 1.1. Multiplication Principle (AND) If an event can occur in $m$ ways and a second independent event can occur in $n$ ways, then the two events can occur in $m \times n$ ways. Example: Choosing a shirt (3 options) AND pants (2 options) gives $3 \times 2 = 6$ outfits. 1.2. Addition Principle (OR) If an event can occur in $m$ ways and a second mutually exclusive event can occur in $n$ ways, then one or the other event can occur in $m + n$ ways. Example: Choosing a shirt (3 options) OR a jacket (2 options) gives $3 + 2 = 5$ choices. 2. Factorials The product of all positive integers less than or equal to an integer $n$. Notation: $n!$ Formula: $n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1$ Special Cases: $0! = 1$ $1! = 1$ Example: $4! = 4 \times 3 \times 2 \times 1 = 24$ 3. Permutations (Order Matters) 3.1. Definition An arrangement of objects in a specific order. Used when the sequence or position of items is important. 3.2. 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 people in a line: $P(5, 3) = \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{120}{2} = 60$ ways. 3.3. Permutations of $n$ distinct objects (all at once) Formula: $P(n, n) = n!$ Example: Arranging 4 books on a shelf: $4! = 24$ ways. 3.4. Permutations with Repetition (Objects are not distinct) If there are $n$ objects where $n_1$ are alike of one kind, $n_2$ are alike of another kind, ..., $n_k$ are alike of a $k$-th kind, the number of distinct permutations is: Formula: $P = \frac{n!}{n_1! n_2! \dots n_k!}$ Example: Arranging the letters in "MISSISSIPPI" ($n=11$, M=1, I=4, S=4, P=2): $\frac{11!}{1!4!4!2!} = 34650$ ways. 3.5. Circular Permutations Arrangement of $n$ distinct objects in a circle. Formula: $(n-1)!$ Example: Arranging 5 people around a circular table: $(5-1)! = 4! = 24$ ways. If clockwise and anti-clockwise arrangements are considered the same (e.g., beads on a necklace): $\frac{(n-1)!}{2}$ 4. Combinations (Order Does Not Matter) 4.1. Definition A selection of objects where the order of selection is not important. Used when forming groups or sets. 4.2. Combinations of $n$ distinct objects taken $r$ at a time Notation: $C(n, r)$, $_nC_r$, or $\binom{n}{r}$ Formula: $C(n, r) = \frac{n!}{r!(n-r)!}$ Relationship with Permutations: $C(n, r) = \frac{P(n, r)}{r!}$ Example: Choosing 3 students from a group of 5 for a committee: $C(5, 3) = \frac{5!}{3!(5-3)!} = \frac{5!}{3!2!} = \frac{120}{6 \times 24} = 10$ ways. 4.3. Properties of Combinations $C(n, 0) = 1$ (There's one way to choose zero items: choose nothing) $C(n, n) = 1$ (There's one way to choose all items) $C(n, r) = C(n, n-r)$ (Choosing $r$ items is the same as choosing to leave $n-r$ items) 5. Combinations with Repetition (Stars and Bars) Number of ways to choose $r$ items from $n$ types of items with repetition allowed. Formula: $C(n+r-1, r) = \binom{n+r-1}{r}$ This is equivalent to distributing $r$ identical items into $n$ distinct bins. Example: Choosing 3 scoops of ice cream from 5 available flavors (repetition allowed): $n=5$ (flavors), $r=3$ (scoops). $C(5+3-1, 3) = C(7, 3) = \frac{7!}{3!4!} = \frac{5040}{6 \times 24} = 35$ ways. 6. JEE Specific Topics & Advanced Concepts 6.1. Distribution of Identical & Distinct Objects Identical objects into Distinct bins ($n$ objects, $r$ bins): Any number of items in each bin: $\binom{n+r-1}{r-1}$ (using stars and bars) Each bin has at least one item: $\binom{n-1}{r-1}$ Distinct objects into Distinct bins ($n$ objects, $r$ bins): Any number of items in each bin: $r^n$ Each bin has at most one item: $P(r, n)$ Distinct objects into Identical bins: Use Stirling numbers of the second kind (usually given or derived for small values). 6.2. Derangements A permutation of $n$ objects such that no object appears in its original position. Notation: $D_n$ or $!n$ Formula: $D_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + (-1)^n \frac{1}{n!} \right)$ Recursive Formula: $D_n = (n-1)(D_{n-1} + D_{n-2})$ for $n \ge 2$, with $D_0=1, D_1=0$. Values: $D_2=1, D_3=2, D_4=9, D_5=44$. 6.3. Multinomial Theorem Coefficient The coefficient of $x_1^{k_1} x_2^{k_2} \dots x_m^{k_m}$ in the expansion of $(x_1 + x_2 + \dots + x_m)^n$ where $k_1 + k_2 + \dots + k_m = n$. Formula: $\frac{n!}{k_1! k_2! \dots k_m!}$ This is also the number of ways to arrange $n$ objects where $k_1$ are of type 1, $k_2$ of type 2, etc. 6.4. Gap Method & Tie Method Gap Method: Used when certain objects must NOT be together. Arrange the objects that can be together. Create 'gaps' between them and at the ends. Place the forbidden objects into these gaps. Tie Method (Block Method): Used when certain objects MUST be together. Treat the objects that must be together as a single block. Arrange this block with other objects. Arrange the objects within the block. 6.5. Divisors of a Number If $N = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$ is the prime factorization of $N$. Number of divisors: $(a_1+1)(a_2+1)\dots(a_k+1)$ Sum of divisors: $(1+p_1+\dots+p_1^{a_1})\dots(1+p_k+\dots+p_k^{a_k})$ Number of ways to express $N$ as a product of two factors: $\frac{1}{2} \times (\text{number of divisors})$ if $N$ is not a perfect square, or $\frac{1}{2} \times ((\text{number of divisors})+1)$ if $N$ is a perfect square. 6.6. Grid Problems / Path Counting Number of shortest paths from $(0,0)$ to $(m,n)$ on a grid: $C(m+n, m)$ or $C(m+n, n)$. This is equivalent to arranging $m$ 'Right' moves and $n$ 'Up' moves. 7. Key Distinctions Feature Permutation Combination Order Matters (e.g., ABC $\neq$ ACB) Does not matter (e.g., {A, B, C} = {A, C, B}) Keyword Arrangement, order, sequence, position, distinct roles Selection, group, choose, committee, set Formula (no repetition) $\frac{n!}{(n-r)!}$ $\frac{n!}{r!(n-r)!}$ Repetition $\frac{n!}{n_1! n_2! \dots}$ (for distinct objects with some identical) $\binom{n+r-1}{r}$ (for choosing with replacement)