Permutation & Combination

Cheatsheet Content

### Introduction to Permutation & Combination Permutation and Combination are fundamental concepts in combinatorics, used to count the number of ways to arrange or select items from a set. They are crucial for solving problems in probability, statistics, and various aptitude tests. - **Permutation (Arrangement):** Deals with the arrangement of objects where the order matters. - **Combination (Selection):** Deals with the selection of objects where the order does not matter. ### Fundamental Counting Principles #### 1. Multiplication Principle If an event can occur in $m$ different ways, and following it, another event can occur in $n$ different ways, then the total number of ways both events can occur in a specific order is $m \times n$. - **Example:** If you have 3 shirts and 2 pants, you can make $3 \times 2 = 6$ different outfits. #### 2. Addition Principle If an event can occur in $m$ different ways, and another event can occur in $n$ different ways, and these two events cannot occur simultaneously, then the total number of ways either event can occur is $m + n$. - **Example:** If you can choose a cake from 5 types OR a pastry from 3 types, you have $5 + 3 = 8$ choices. ### Factorial Notation The product of all positive integers less than or equal to a given positive integer $n$ is called $n$ factorial, denoted by $n!$. - **Definition:** $n! = n \times (n-1) \times (n-2) \times ... \times 3 \times 2 \times 1$ - **Special Cases:** - $0! = 1$ - $1! = 1$ - **Examples:** - $3! = 3 \times 2 \times 1 = 6$ - $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ ### Permutations #### 1. Permutations of $n$ distinct objects taken $r$ at a time The number of arrangements of $n$ distinct objects taken $r$ at a time is given by the formula: $$ P(n, r) = \frac{n!}{(n-r)!} $$ - **Condition:** $0 \le r \le n$ - **Example:** How many ways can you arrange 3 books from a set of 5 distinct books? $P(5, 3) = \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{120}{2} = 60$ ways. #### 2. Permutations of $n$ distinct objects taken all at a time If $r=n$, the formula simplifies to: $$ P(n, n) = n! $$ - **Example:** How many ways can 4 distinct people be arranged in a line? $P(4, 4) = 4! = 4 \times 3 \times 2 \times 1 = 24$ ways. #### 3. Permutations with Repetition (Objects are not distinct) The number of distinct permutations of $n$ objects where $p_1$ objects are of one type, $p_2$ objects are of a second type, ..., $p_k$ objects are of a $k^{th}$ type is: $$ P = \frac{n!}{p_1! p_2! ... p_k!} $$ - **Condition:** $p_1 + p_2 + ... + p_k = n$ - **Example:** How many distinct permutations of the letters in the word "MISSISSIPPI"? - $n = 11$ (total letters) - M: 1, I: 4, S: 4, P: 2 $$ P = \frac{11!}{1! 4! 4! 2!} = \frac{39916800}{1 \times 24 \times 24 \times 2} = 34650 $$ #### 4. Circular Permutations - **Case 1: Distinct objects arranged in a circle** The number of ways to arrange $n$ distinct objects in a circle is $(n-1)!$. - **Example:** How many ways can 5 people be seated around a circular table? $(5-1)! = 4! = 24$ ways. - **Case 2: Objects arranged in a circle where clockwise and anti-clockwise arrangements are considered the same** (e.g., beads in a necklace, flowers in a garland) The number of arrangements is $\frac{(n-1)!}{2}$. - **Example:** How many different necklaces can be made from 6 distinct beads? $\frac{(6-1)!}{2} = \frac{5!}{2} = \frac{120}{2} = 60$ ways. ### Combinations #### 1. Combinations of $n$ distinct objects taken $r$ at a time The number of ways to select $r$ objects from a set of $n$ distinct objects (where order does not matter) is given by the formula: $$ C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!} $$ - **Condition:** $0 \le r \le n$ - **Relationship with Permutation:** $C(n, r) = \frac{P(n, r)}{r!}$ - **Example:** How many ways can you choose 3 students from a group of 8 students? $$ C(8, 3) = \frac{8!}{3!(8-3)!} = \frac{8!}{3!5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56 $$ #### 2. Properties of Combinations - $C(n, 0) = 1$ (There is 1 way to choose 0 items: choose nothing) - $C(n, n) = 1$ (There is 1 way to choose all $n$ items) - $C(n, 1) = n$ (There are $n$ ways to choose 1 item) - $C(n, r) = C(n, n-r)$ - **Example:** $C(10, 3) = C(10, 7)$ $$ C(10, 3) = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120 $$ $$ C(10, 7) = \frac{10!}{7!3!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120 $$ #### 3. Combinations with Repetition The number of ways to choose $r$ items from $n$ types of items with repetition allowed is: $$ C(n+r-1, r) $$ - **Example:** How many ways can you select 3 ice cream scoops from 5 available flavors, with repetition allowed? $$ C(5+3-1, 3) = C(7, 3) = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35 $$ ### Common Aptitude Problems #### 1. Committee Formation - **Scenario:** Selecting a group of people from a larger group. Order does not matter. - **Approach:** Use combinations. - **Example:** A committee of 3 men and 2 women is to be formed from 7 men and 5 women. - Ways to choose men: $C(7, 3) = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ - Ways to choose women: $C(5, 2) = \frac{5 \times 4}{2 \times 1} = 10$ - Total ways (Multiplication Principle): $35 \times 10 = 350$ #### 2. Word Problems (Arrangement of letters) - **Scenario:** Arranging letters of a word. Order matters. - **Approach:** Use permutations. If letters are repeated, use permutation with repetition. - **Example:** How many words can be formed using the letters of the word "APPLE"? - $n=5$ letters. P is repeated 2 times. $$ \frac{5!}{2!} = \frac{120}{2} = 60 $$ #### 3. Number Formation - **Scenario:** Forming numbers using given digits. Order matters. - **Approach:** Use permutations or direct counting (boxes method). Consider restrictions (e.g., even/odd, no repetition). - **Example:** How many 3-digit numbers can be formed using digits 1, 2, 3, 4, 5 without repetition? - Hundreds place: 5 choices - Tens place: 4 choices (one used) - Units place: 3 choices (two used) - Total: $5 \times 4 \times 3 = 60$ (or $P(5, 3) = 60$) - **Example:** How many 3-digit even numbers can be formed using digits 1, 2, 3, 4, 5 without repetition? - Units place (must be even): 2 choices (2 or 4) - Hundreds place: 4 choices (one used for unit, one remaining from 5) - Tens place: 3 choices (two used) - Total: $4 \times 3 \times 2 = 24$ #### 4. Seating Arrangements - **Scenario:** Arranging people in a row or around a table. Order matters. - **Approach:** Use permutations (linear or circular). - **Example:** In how many ways can 6 people be seated in a row such that two particular people always sit together? - Treat the two particular people as one unit. Now there are $5$ units to arrange: $(P_1P_2), P_3, P_4, P_5, P_6$. - Arrangement of 5 units: $5! = 120$ - The two particular people can arrange themselves in $2! = 2$ ways within their unit. - Total ways: $120 \times 2 = 240$ #### 5. Grid Paths (Combinations with Repetition) - **Scenario:** Finding the number of shortest paths on a grid. - **Approach:** If you need to move 'R' steps right and 'D' steps down, the total steps are $R+D$. The problem is to arrange $R$ 'R's and $D$ 'D's. - **Formula:** $\frac{(R+D)!}{R! D!}$ (This is equivalent to $C(R+D, R)$ or $C(R+D, D)$) - **Example:** How many shortest paths from (0,0) to (3,2)? - Need 3 Right moves (R) and 2 Down moves (D). Total 5 moves. $$ \frac{5!}{3!2!} = \frac{120}{6 \times 2} = 10 $$ #### 6. Handshakes / Diagonals - **Scenario:** Number of handshakes between $n$ people, or number of diagonals in a polygon with $n$ vertices. - **Approach:** These are combination problems where 2 items are chosen from $n$. - **Handshakes:** $C(n, 2) = \frac{n(n-1)}{2}$ - **Diagonals:** $C(n, 2) - n$ (Total lines between vertices minus the $n$ sides) - **Example (Handshakes):** In a party of 10 people, everyone shakes hand with everyone else. How many handshakes? $$ C(10, 2) = \frac{10 \times 9}{2} = 45 $$ - **Example (Diagonals):** How many diagonals does a hexagon have? ($n=6$) $$ C(6, 2) - 6 = \frac{6 \times 5}{2} - 6 = 15 - 6 = 9 $$ ### Tips and Tricks 1. **Identify if Order Matters:** - **Permutation (Order Matters):** Arrangements, rankings, seating, forming numbers/words, distinct positions (e.g., President, VP). - **Combination (Order Doesn't Matter):** Selections, groups, committees, teams, choosing items from a menu, identical positions. - **Keywords:** "arrange", "order", "position" (Permutation); "select", "choose", "group", "committee" (Combination). 2. **"AND" vs. "OR":** - **"AND" (both events occur):** Use Multiplication Principle ($\times$). - **"OR" (either event occurs):** Use Addition Principle ($+$). 3. **"At Least" / "At Most" Problems:** - **"At least one":** Often easier to calculate "Total ways - Ways with none". - Example: Ways to select at least one girl from 5 girls and 3 boys. Total ways - Ways to select only boys = $C(8, k) - C(3, k)$ (where k is total selection) OR $2^n - 1$ for at least one from n items. - **"At most $k$":** Sum of ways for $0, 1, ..., k$ items. - Example: At most 2 girls: Ways with 0 girls + Ways with 1 girl + Ways with 2 girls. 4. **Restrictions First:** Address any restrictions or conditions (e.g., specific items must be included/excluded, digits must be even/odd, items must sit together) before applying general formulas. 5. **Complementary Counting:** Sometimes, counting what you *don't* want and subtracting it from the total is easier. - Total arrangements - arrangements where condition is *not* met. 6. **"Gap Method" for "Never Together" Problems:** - To arrange $n$ items such that $k$ specific items are never together: 1. Arrange the $(n-k)$ items first. This creates $(n-k+1)$ gaps. 2. Place the $k$ specific items into $k$ of these gaps. - **Example:** 5 boys and 3 girls, girls never sit together. 1. Arrange 5 boys: $5!$ ways. (B_B_B_B_B) -> 6 gaps 2. Place 3 girls in 3 of the 6 gaps: $P(6, 3)$ ways. 3. Total ways: $5! \times P(6, 3) = 120 \times (6 \times 5 \times 4) = 120 \times 120 = 14400$. 7. **Combinations vs. Partitions:** - **Combinations:** Selecting items. - **Partitions:** Dividing items into groups. - If groups are distinct (e.g., Group A, Group B), use multiplication principle for each selection. - If groups are identical (e.g., just two groups of 3), divide by $k!$ if $k$ groups have the same size. - **Example:** Divide 6 people into two groups of 3. - Choose 3 for first group: $C(6,3)$ - Choose 3 for second group: $C(3,3)$ - Since groups are identical, divide by $2!$: $\frac{C(6,3) \times C(3,3)}{2!} = \frac{20 \times 1}{2} = 10$.