Permutations and Combinations revision notes

Fundamental Principle of Counting

The foundation of all counting techniques is determining the number of ways to arrange and select objects without actually listing them.

• The Multiplication Principle: If an event can occur in $m$ different ways, following which another event can occur in $n$ different ways, then the total number of occurrences of the events in the given order is $m \times n$. This generalizes to any finite number of sequential events (e.g., $m \times n \times p$). → [JEE TIP] Use this when events are dependent and happen in sequence (indicated by the word "AND").
• The Addition Principle: While not explicitly named in the text, it is utilized when breaking down mutually exclusive cases. For example, if generating a signal requires 2 OR 3 OR 4 OR 5 flags, we calculate the arrangements for each case separately and add them up (e.g., $20 + 60 + 120 + 120 = 320$). → [JEE TIP] Use this for mutually exclusive cases (indicated by the word "OR").

Factorial Notation

The notation $n!$ represents the product of the first $n$ natural numbers: $n! = 1 \times 2 \times 3 \times ... \times (n-1) \times n$.

• Recursive Property: $n! = n(n-1)!$ (for $n \ge 2$). This property is heavily used for simplifying factorial fractions.
• Zero Factorial: By definition, $0! = 1$. This ensures combinatorial formulas remain valid even for zero values (e.g., selecting or arranging 0 objects).

Permutations (Arrangements)

A permutation is an arrangement in a definite order of a number of objects taken some or all at a time. Order is strictly important here.

• Permutations of Distinct Objects (No Repetition): The number of permutations of $n$ different objects taken $r$ at a time ($0 < r \le n$) is denoted by $^nP_r$.
  • Formula: $^nP_r = \frac{n!}{(n-r)!}$.
  • When arranging all $n$ objects at once ($r=n$), the number of ways is $^nP_n = n!$.
  • Arranging 0 objects is considered 1 way: $^nP_0 = 1$.
• Permutations with Repetition Allowed: The number of permutations of $n$ different objects taken $r$ at a time, where repetition is allowed, is $n^r$.
• Permutations of Identical Objects: The number of permutations of $n$ objects, where $p_1$ objects are of one kind, $p_2$ are of a second kind, ..., $p_k$ are of a $k^{th}$ kind, and the rest are all different, is $\frac{n!}{p_1! p_2! ... p_k!}$. → [JEE TIP] Whenever dealing with words like "MISSISSIPPI" or "ALLAHABAD", immediately count the frequencies of identical letters before applying this formula.

Combinations (Selections)

A combination is a selection of items where the order of selection does not matter (e.g., choosing a team of players, drawing chords between points).

• Combinations of Distinct Objects: The number of combinations of $n$ different objects taken $r$ at a time is denoted by $^nC_r$.
  • Formula: $^nC_r = \frac{n!}{r!(n-r)!}$.
• Relationship between Permutations and Combinations: Every combination of $r$ objects can be rearranged internally in $r!$ ways. Therefore, $^nP_r = ^nC_r \times r!$ ($0 < r \le n$).
• Key Properties of Combinations:
  1. $^nC_0 = 1$ (Selecting 0 objects means leaving all behind, which is 1 way).
  2. $^nC_n = 1$.
  3. Complementary Combinations: $^nC_r = ^nC_{n-r}$. Selecting $r$ objects is identical to rejecting the remaining $(n-r)$ objects.
  4. Equality Rule: If $^nC_a = ^nC_b$, then either $a = b$ or $a = n - b$ (which implies $n = a + b$). → [JEE TIP] Highly tested property in basic JEE algebra equations.
  5. Pascal's Rule: $^nC_r + ^nC_{r-1} = ^{n+1}C_r$.

JEE Advanced Topics

• Circular Permutations: The number of ways to arrange $n$ distinct objects in a circle is $(n-1)!$. If clockwise and counter-clockwise arrangements are indistinguishable (like beads on a necklace or flowers in a garland), the number of ways is $\frac{(n-1)!}{2}$.
• Beggars Method (Stars and Bars): To find the number of non-negative integral solutions to the equation $x_1 + x_2 + ... + x_r = n$, the formula is $^{n+r-1}C_{r-1}$. For strictly positive integral solutions, the formula is $^{n-1}C_{r-1}$.
• Derangements: The number of ways $n$ items can be placed into $n$ distinct directed positions such that NO item goes to its original/correct position is $D_n = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + ... + \frac{(-1)^n}{n!}\right)$.
• Legendre's Formula: To find the highest power (exponent) of a prime number $p$ that divides $n!$, use $E_p(n!) = \lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \lfloor \frac{n}{p^3} \rfloor + ...$
• Distribution into Groups: Distributing $m+n+p$ distinct items into three groups of sizes $m, n, p$ is $\frac{(m+n+p)!}{m!n!p!}$. If group sizes are identical ($m=n=p$), divide by the factorial of the number of identical groups to avoid overcounting: $\frac{(3m)!}{(m!)^3 3!}$.

Key Concepts & Definitions

Permutation:

An arrangement of objects in a definite sequential order.

Combination:

A selection of objects where order is entirely irrelevant (e.g., XYXYXY and YXYXYX are the same combination).

Multiplication Principle vs. Addition Principle:

Multiplication represents successive events (Event A occurs and then Event B occurs), while Addition represents alternate events (Either Event A or Event B occurs).

Formulae, Equations & Variables

• $n! = n(n-1)!$
  • $n$: Must be a non-negative integer ($\mathbb{W}$).
• $^nP_r = \frac{n!}{(n-r)!}$
  • $n$: Total number of distinct objects available.
  • $r$: Number of objects to be arranged.
  • Condition: $n \ge r \ge 0$; $n \in \mathbb{N}$, $r \in \mathbb{W}$.
• $^nC_r = \frac{n!}{r!(n-r)!}$
  • $n$: Total distinct objects.
  • $r$: Number of objects to select.
  • Condition: $n \ge r \ge 0$; $n \in \mathbb{N}$, $r \in \mathbb{W}$.
• Permutations with Indistinguishable Objects: $\frac{n!}{p_1! p_2! ... p_k!}$
  • $n$: Total objects.
  • $p_k$: Frequency of the $k^{th}$ type of identical object.

Conditions & Limitations

• Formulas for $^nP_r$ and $^nC_r$ cannot be used if the total pool of $n$ objects contains duplicates (indistinguishable items) unless modified.
• The Factorial operator $!$ is strictly limited to non-negative integers. Negative factorials and fractional factorials are undefined in the context of standard P&C.
• Zero can be tricky. When forming numbers of a specific length (e.g., 3-digit numbers), a "0" in the most significant digit (hundreds place) disqualifies the number from being a 3-digit number. It acts as a 2-digit number and must be subtracted out. → [JEE TIP] Always check if 0 is part of the given digits when forming numerical sequences!

Standard Derivations & Step-by-Step Problem Solving

1. Tie Method (Bundle Method)

Use case: When specific items (like vowels) must always occur "together". Steps:

1. Group the required items into a single "bundle" or "super-object".
2. Count the total arrangements of the remaining objects plus this 1 super-object.
3. Multiply the result by the internal permutations of the items inside the bundle.

2. Gap Method

Use case: When specific items (like boys) must "never occur together" (no two are adjacent). Steps:

1. Arrange the other non-restricted items first (e.g., the girls). Let's say there are $n$ girls. This gives $n!$ ways.
2. Create "gaps" between and at the ends of these arranged items. For $n$ items, there are $n+1$ gaps.
3. Select and arrange the restricted items into these gaps using $^{n+1}P_r$. Multiply the two values. → [JEE TIP] Never use Total minus 'All Together' for finding "no two are together" if the restricted objects are more than 2, as it leaves cases where some (but not all) are together.

3. Dictionary Rank Problem

Use case: Finding the alphabetical rank of a given word (e.g., "AGAIN" finding the 50th word). Steps:

1. Arrange the letters of the word alphabetically (A, A, G, I, N).
2. Fix the first letter and find permutations of the remaining letters. (e.g., Words starting with A = $4! = 24$).
3. Systematically step through the alphabet for the first position until you get close to the target rank, then move to the second position.

Previous Year JEE Topics

• Dictionary Rank of Words (with and without repetition).
• Number of factors/divisors and sum of divisors.
• Grid problems (shortest paths from $(0,0)$ to $(m,n)$).
• Selection of specific suits/denominations from playing cards.
• Distribution of distinct and identical objects (Beggars method).
• Gap method and Bundle method restrictions.

Top 10 JEE MCQ Traps

Trap 1 - Zero as a Leading Digit:

• [JEE TIP] Trap 1 - The Leading Zero Illusion:

  • Misconception: Permutations generated from a set of digits that include $0$ (such as $0, 4, 2$) automatically yield valid $n$-digit numbers.
  • Correct Understanding: A number cannot have $0$ as its leading digit if it is to retain its specified number of digits (e.g., $042$ is a 2-digit number, not a 3-digit number). To solve this correctly, you must manually fix $0$ at the highest place value, calculate those specific permutations, and subtract them from the total unconstrained permutation count.

• [JEE TIP] Trap 2 - The Separated Vowel Semantic Split:

  • Misconception: Subtracting the cases where "all vowels are together" from the "total possible arrangements" yields the correct answer for "no two vowels are together".
  • Correct Understanding: Subtracting "all together" only eliminates the single block case where every vowel sits next to each other; it completely misses cases where two vowels are together and a third is separated. To guarantee that no two vowels sit together, you must instead use the Gap Method—arrange the consonants first, and then choose spaces from the resulting gaps to place the vowels.

• [JEE TIP] Trap 3 - Identical Combination Over-Selection:

  • Misconception: The standard combination formula ${}^n\text{C}_r$ can be applied directly to select a subset of letters from a word containing repeating characters, such as "INDEPENDENCE".
  • Correct Understanding: The formula ${}^n\text{C}_r$ is strictly restricted to distinct objects. When dealing with collections that contain identical objects, you must construct mutually exclusive, exhaustive cases based on structural patterns (e.g., Case 1: 3 letters are identical; Case 2: 2 letters are identical and 1 is different; Case 3: All 3 letters are completely different) and calculate each separately.

• [JEE TIP] Trap 4 - The 3D Necklace Rotation Inversion:

  • Misconception: Arranging $n$ distinct beads on a circular necklace follows the standard circular permutation formula $(n-1)!$.
  • Correct Understanding: A physical necklace can be flipped over in 3D space, which means that its clockwise and counter-clockwise arrangements are visually and geometrically identical. Because turning the necklace over mirrors the sequence, you must divide the unconstrained circular permutations by 2, yielding $\frac{(n-1)!}{2}$.

• [JEE TIP] Trap 5 - The "At Least One" Sigma Exhaustion:

  • Misconception: Finding the number of ways to select "at least one" object from a set of $n$ distinct items requires manually computing and summing individual combinations (${}^n\text{C}_1 + {}^n\text{C}_2 + {}^n\text{C}_3 + \dots + {}^n\text{C}_n$).
  • Correct Understanding: Summing every term individually is highly inefficient and prone to addition errors under exam pressure. Instead, exploit the total subset identity: since each distinct object has exactly 2 choices (either selected or not selected), the entire sum condenses perfectly to $2^n - 1$ (total possible subsets minus the single empty null set).

• [JEE TIP] Trap 6 - The Unmarked Box Division Deficit:

  • Misconception: Distributing $12$ distinct items equally into $3$ identical, unmarked boxes can be computed directly using the multinomial coefficient $\frac{12!}{4!4!4!}$.
  • Correct Understanding: The multinomial coefficient implicitly assumes that the boxes themselves are distinct (e.g., Box A, Box B, Box C). If the boxes are completely unmarked and identical, swapping the final groups between the boxes does not create a new unique distribution. To remove this false ordering, you must divide by the factorial of the number of identical groups, giving $\frac{12!}{(4!)^3 \cdot 3!}$.

• [JEE TIP] Trap 7 - Card Suit Logical Disjunction vs. Conjunction:

  • Misconception: The counting operations for selecting cards "of the same suit" and cards "of different suits" are interchangeable.
  • Correct Understanding: The wording dictates the mathematical operator. Selecting 4 cards of the same suit implies an OR relationship (4 Hearts OR 4 Clubs OR 4 Diamonds OR 4 Spades), which requires the addition rule: $({}^{13}\text{C}_4) + ({}^{13}\text{C}_4) + ({}^{13}\text{C}_4) + ({}^{13}\text{C}_4)$. Selecting 4 cards of different suits implies an AND relationship (1 Heart AND 1 Club AND 1 Diamond AND 1 Spade), which mandates the multiplication rule: $({}^{13}\text{C}_1) \times ({}^{13}\text{C}_1) \times ({}^{13}\text{C}_1) \times ({}^{13}\text{C}_1)$.

• [JEE TIP] Trap 8 - The Polynomial Factorial Expansion Trap:

  • Misconception: Solving a combination equality like ${}^n\text{C}_8 = {}^n\text{C}_2$ requires expanding the terms into full factorials and solving the resulting high-degree algebraic polynomial for $n$.
  • Correct Understanding: Do not expand the factorials. Instead, apply the fundamental complementary combination property: ${}^n\text{C}_a = {}^n\text{C}_b \implies$ either $a = b$ or $n = a + b$. Since $8 \neq 2$, it must hold true that $n = 8 + 2 = 10$, bypassing the algebraic expansion entirely.

• [JEE TIP] Trap 9 - Manual Derangement Counting Exhaustion:

  • Misconception: Determining the number of ways to place $n$ distinct letters into $n$ distinct envelopes such that no letter goes into its correct envelope is best computed by manual tree diagrams or basic subtraction.
  • Correct Understanding: Counting derangements manually for $n \ge 4$ is highly prone to omissions. You should directly apply the formal Derangement formula: $\text{D}_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + (-1)^n\frac{1}{n!} \right)$. For the exam, it is highly efficient to memorize the standard output values: $\text{D}_3 = 2$, $\text{D}_4 = 9$, and $\text{D}_5 = 44$.

• [JEE TIP] Trap 10 - The Selection-Arrangement Chronological Blending:

  • Misconception: Selecting and ordering a team under constraints (such as a 5-member committee with "at least one boy and one girl") can be solved cleanly using a single unified permutation formula.
  • Correct Understanding: Attempting to select and arrange items simultaneously when conditions apply leads to severe double-counting errors. You must break the problem down into two discrete, chronological phases: Phase 1 (Selection)—use combinations to pick the items, summing up the independent, mutually exclusive case structures. Phase 2 (Arrangement)—multiply the final consolidated selection count by $r!$ to order them if the positions are distinct.