Permutations & Combinations
A JEE favourite — master counting principles, permutations with restrictions, combinations, distribution problems, and derangements with competitive exam tricks.
0% complete5 units
01
Fundamental Counting Principle
Addition and multiplication principles — the foundation of all counting arguments in JEE.
Multiplication & Addition Principles
Multiplication Principle
If a task can be performed in two stages, where the first stage has $m$ choices and the second has $n$ choices (independent of the first), the total number of ways $= m \times n$.
Addition Principle
If a task can be performed by method A ($m$ ways) OR method B ($n$ ways), and the methods are mutually exclusive, total ways $= m + n$.
JEE Trick — Complementary Counting
When "at least one" or "at least two" conditions appear, use:
(Desired count) $=$ (Total) $-$ (Undesired count).
This is often much faster than direct counting.
(Desired count) $=$ (Total) $-$ (Undesired count).
This is often much faster than direct counting.
📝 Example
How many 4-digit numbers are there with at least one digit repeated?
Total 4-digit numbers: $9 \times 10 \times 10 \times 10 = 9000$.
4-digit numbers with no repetition: $9 \times 9 \times 8 \times 7 = 4536$.
At least one repetition: $9000 - 4536 = \boxed{4464}$.
4-digit numbers with no repetition: $9 \times 9 \times 8 \times 7 = 4536$.
At least one repetition: $9000 - 4536 = \boxed{4464}$.
02
Permutations
Arrangements: ${}^nP_r$, permutations with repetition, identical objects, and circular permutations.
Linear Permutations
Permutation
An arrangement of $r$ objects from $n$ distinct objects:
${}^nP_r = \frac{n!}{(n-r)!}$, $\quad 0 \leq r \leq n$.
${}^nP_r = \frac{n!}{(n-r)!}$, $\quad 0 \leq r \leq n$.
Permutations with Identical Objects
The number of permutations of $n$ objects where $p$ are of one kind, $q$ of another, etc.:
$\frac{n!}{p! \cdot q! \cdot r! \cdots}$
$\frac{n!}{p! \cdot q! \cdot r! \cdots}$
Permutations with Repetition
Arranging $r$ objects from $n$ types (repetition allowed): $n^r$.
JEE Tip: For number-formation problems, always handle the leading digit separately (it cannot be $0$).
JEE Tip: For number-formation problems, always handle the leading digit separately (it cannot be $0$).
📝 Example
How many words (with or without meaning) can be formed using all letters of "MISSISSIPPI"?
Letters: M(1), I(4), S(4), P(2). Total = 11 letters.
Arrangements $= \frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = \frac{39916800}{1 \times 24 \times 24 \times 2} = \frac{39916800}{1152} = \boxed{34650}$.
Arrangements $= \frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = \frac{39916800}{1 \times 24 \times 24 \times 2} = \frac{39916800}{1152} = \boxed{34650}$.
Circular Permutations
Circular Arrangements
$n$ distinct objects in a circle: $(n-1)!$ ways.
If clockwise and anticlockwise are same (e.g., necklace, bracelet): $\frac{(n-1)!}{2}$.
If clockwise and anticlockwise are same (e.g., necklace, bracelet): $\frac{(n-1)!}{2}$.
JEE Trick — Fixing One Position
In circular permutations, fix one person/object to remove the rotational symmetry, then arrange the rest linearly. This simplifies restricted circular arrangement problems.
📝 Example
In how many ways can 8 people sit around a table such that two specific people A and B are always adjacent?
Treat A and B as one block. Now 7 entities around a circle: $(7-1)! = 6! = 720$. A and B can swap within the block: $2!$ ways. Total $= 720 \times 2 = \boxed{1440}$.
03
Combinations
Selection: ${}^nC_r$, properties, Pascal's triangle, and combination identities for JEE.
Combinations & Properties
Combination
A selection of $r$ objects from $n$ distinct objects (order doesn't matter):
${}^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}$
${}^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}$
Key Properties
$\binom{n}{r} = \binom{n}{n-r}$ (symmetry)
$\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}$ (Pascal's rule)
$\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n$
$\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \cdots = 0$
$\binom{n}{1} + 2\binom{n}{2} + 3\binom{n}{3} + \cdots + n\binom{n}{n} = n \cdot 2^{n-1}$
$\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}$ (Pascal's rule)
$\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n$
$\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \cdots = 0$
$\binom{n}{1} + 2\binom{n}{2} + 3\binom{n}{3} + \cdots + n\binom{n}{n} = n \cdot 2^{n-1}$
JEE Shortcut — ${}^nC_r = {}^nC_s$ Implies
$r = s$ or $r + s = n$. This is used extensively to solve equations involving binomial coefficients.
Vandermonde's Identity
$\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$
JEE Application: Used in problems where selection is from two groups.
JEE Application: Used in problems where selection is from two groups.
📝 Example
From 6 boys and 4 girls, a committee of 5 is to be formed with at least 2 girls. How many ways?
At least 2 girls = (2G, 3B) + (3G, 2B) + (4G, 1B).
$= \binom{4}{2}\binom{6}{3} + \binom{4}{3}\binom{6}{2} + \binom{4}{4}\binom{6}{1}$
$= 6 \times 20 + 4 \times 15 + 1 \times 6 = 120 + 60 + 6 = \boxed{186}$.
$= \binom{4}{2}\binom{6}{3} + \binom{4}{3}\binom{6}{2} + \binom{4}{4}\binom{6}{1}$
$= 6 \times 20 + 4 \times 15 + 1 \times 6 = 120 + 60 + 6 = \boxed{186}$.
04
Distribution Problems
Balls in boxes, stars and bars, derangements — classic JEE Advanced problems.
Distribution & Derangements
Stars and Bars (Identical Objects, Distinct Boxes)
Distribute $n$ identical objects into $r$ distinct boxes:
Each box can be empty: $\binom{n+r-1}{r-1}$
Each box has at least one: $\binom{n-1}{r-1}$
Each box can be empty: $\binom{n+r-1}{r-1}$
Each box has at least one: $\binom{n-1}{r-1}$
Distinct Objects into Distinct Boxes
Each object has $r$ choices: $r^n$ total distributions.
With each box non-empty: use inclusion-exclusion (surjections).
With each box non-empty: use inclusion-exclusion (surjections).
Derangement
A permutation where no element is in its original position. The number of derangements of $n$ elements:
$D_n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n\frac{1}{n!}\right)$
First few values: $D_1 = 0$, $D_2 = 1$, $D_3 = 2$, $D_4 = 9$, $D_5 = 44$.
$D_n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n\frac{1}{n!}\right)$
First few values: $D_1 = 0$, $D_2 = 1$, $D_3 = 2$, $D_4 = 9$, $D_5 = 44$.
JEE Trick — Partial Derangements
If exactly $k$ objects are in their correct positions:
Choose which $k$ are correct: $\binom{n}{k}$, then derange the rest: $D_{n-k}$.
Total $= \binom{n}{k} \cdot D_{n-k}$.
Choose which $k$ are correct: $\binom{n}{k}$, then derange the rest: $D_{n-k}$.
Total $= \binom{n}{k} \cdot D_{n-k}$.
📝 Example
In how many ways can 5 letters be placed in 5 envelopes such that exactly 2 are in the correct envelopes?
Choose which 2 are correct: $\binom{5}{2} = 10$. Derange the remaining 3: $D_3 = 2$.
Total $= 10 \times 2 = \boxed{20}$.
Total $= 10 \times 2 = \boxed{20}$.
05
Applications — Seating, Selection & Arrangement
Complex JEE problems involving constraints — seating arrangements, selection with conditions, and mixed problems.
Restricted Arrangements & Selections
Gap Method (No Two Adjacent)
To arrange $n$ items such that $k$ specific items are never adjacent: first arrange the other $n-k$ items, then place the $k$ items in the gaps.
If $n-k$ items create $n-k+1$ gaps, choose $k$ of them: $\binom{n-k+1}{k} \times k!$.
If $n-k$ items create $n-k+1$ gaps, choose $k$ of them: $\binom{n-k+1}{k} \times k!$.
Division into Groups
Divide $mn$ objects into $n$ groups of $m$ each:
Distinct groups (labelled): $\frac{(mn)!}{(m!)^n}$
Identical groups (unlabelled): $\frac{(mn)!}{(m!)^n \cdot n!}$
Distinct groups (labelled): $\frac{(mn)!}{(m!)^n}$
Identical groups (unlabelled): $\frac{(mn)!}{(m!)^n \cdot n!}$
JEE Trick — Sum of Digits/Numbers
If you form all $n$-digit numbers from given digits, each digit appears in each position equally often. Use this to find the sum of all such numbers:
Sum $= (\text{sum of digits}) \times (\text{number of times each appears in a position}) \times (111\ldots1)$.
Sum $= (\text{sum of digits}) \times (\text{number of times each appears in a position}) \times (111\ldots1)$.
📝 Example
In a row of 10 seats, in how many ways can 4 people sit so that no two are adjacent?
Place 4 people in non-adjacent seats from 10. First choose the seats: think of 6 empty + 4 occupied. The 6 empty seats create 7 gaps. Choose 4: $\binom{7}{4} = 35$. Then arrange 4 people: $4! = 24$.
Total $= 35 \times 24 = \boxed{840}$.
Total $= 35 \times 24 = \boxed{840}$.
★ Key Takeaways
- Always decide first: is the problem about arrangement (order matters) or selection (order doesn't matter)?
- Complementary counting ("total minus unwanted") is often the fastest approach for "at least" problems.
- For circular permutations, fix one object to break the rotational symmetry.
- Stars and bars: $\binom{n+r-1}{r-1}$ for distributing $n$ identical objects into $r$ distinct boxes.
- Derangements: memorise $D_n = n!(1 - 1/1! + 1/2! - \cdots + (-1)^n/n!)$ and values up to $D_5$.
✎ Practice Problems
Problem 1
How many 5-digit numbers divisible by 5 can be formed using digits $\{0, 1, 2, 3, 4, 5\}$ without repetition?
Show Solution ▼
Case 1: Last digit $= 0$. First 4 digits from $\{1,2,3,4,5\}$: $5 \times 4 \times 3 \times 2 = 120$.
Case 2: Last digit $= 5$. First digit (not $0$ or $5$): 4 choices. Next 3 from remaining 4: $4 \times 3 \times 2 = 24$. Total: $4 \times 24 = 96$.
Answer: $120 + 96 = \boxed{216}$.
Case 2: Last digit $= 5$. First digit (not $0$ or $5$): 4 choices. Next 3 from remaining 4: $4 \times 3 \times 2 = 24$. Total: $4 \times 24 = 96$.
Answer: $120 + 96 = \boxed{216}$.
Problem 2
Find the number of ways to distribute 12 identical balls into 4 distinct boxes such that no box has more than 5 balls.
Show Solution ▼
Without upper bound: $\binom{15}{3} = 455$. Subtract cases where at least one box has $\geq 6$: Let $x_i \geq 6$ for box $i$. Set $y_i = x_i - 6$, then $y_i + \text{rest} = 6$: $\binom{9}{3} = 84$ ways per box. By inclusion-exclusion: $\binom{4}{1} \times 84 - \binom{4}{2} \times \binom{3}{3}(12-12=0, \text{one way}) = 336 - 6 = 330$. Hmm, let's recompute: 2 boxes $\geq 6$ means $y_1+y_2+x_3+x_4 = 0$: $\binom{3}{3} = 1$, times $\binom{4}{2} = 6$. Answer: $455 - 336 + 6 = \boxed{125}$.
Problem 3
In how many ways can the letters of "BANANA" be arranged such that no two N's are adjacent?
Show Solution ▼
BANANA: B(1), A(3), N(2). First arrange B, A, A, A (4 letters): $\frac{4!}{3!} = 4$ ways. This creates 5 gaps: _B_A_A_A_. Place 2 N's in these 5 gaps: $\binom{5}{2} = 10$. Total $= 4 \times 10 = \boxed{40}$.
Problem 4
How many integers between 1 and 1000 (inclusive) are not divisible by 2, 3, or 5?
Show Solution ▼
By inclusion-exclusion:
$|A_2| = 500$, $|A_3| = 333$, $|A_5| = 200$
$|A_2 \cap A_3| = |A_6| = 166$, $|A_2 \cap A_5| = |A_{10}| = 100$, $|A_3 \cap A_5| = |A_{15}| = 66$
$|A_2 \cap A_3 \cap A_5| = |A_{30}| = 33$
$|A_2 \cup A_3 \cup A_5| = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$.
Not divisible by any: $1000 - 734 = \boxed{266}$.
$|A_2| = 500$, $|A_3| = 333$, $|A_5| = 200$
$|A_2 \cap A_3| = |A_6| = 166$, $|A_2 \cap A_5| = |A_{10}| = 100$, $|A_3 \cap A_5| = |A_{15}| = 66$
$|A_2 \cap A_3 \cap A_5| = |A_{30}| = 33$
$|A_2 \cup A_3 \cup A_5| = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$.
Not divisible by any: $1000 - 734 = \boxed{266}$.
Problem 5
Find the number of non-negative integer solutions of $x_1 + x_2 + x_3 + x_4 = 20$ where $x_1 \leq 8$.
Show Solution ▼
Total without restriction: $\binom{23}{3} = 1771$. Solutions with $x_1 \geq 9$: set $y_1 = x_1 - 9$, then $y_1 + x_2 + x_3 + x_4 = 11$: $\binom{14}{3} = 364$.
Answer: $1771 - 364 = \boxed{1407}$.
Answer: $1771 - 364 = \boxed{1407}$.
🎯 Interactive MCQs
1. The number of ways to select 4 letters from the word "PROPORTION" is:
A $\binom{10}{4} = 210$
B $53$
C $45$
D $60$
2. The number of derangements of 6 elements is:
A $264$
B $265$
C $360$
D $44$
3. The number of ways to arrange the letters of "ARRANGE" such that the two R's are never together is:
A $1260$
B $900$
C $660$
D $720$
4. The number of non-negative integer solutions of $x + y + z = 15$ is:
A $120$
B $136$
C $153$
D $105$
5. In how many ways can 5 boys and 5 girls sit alternately around a circular table?
A $2880$
B $14400$
C $576$
D $1440$