Counting Principles — Fundamental Rule, Pigeonhole, Inclusion-Exclusion

The Art of Counting Without Counting

Counting is deceptively simple — until you need to count large numbers of possibilities. How many different passwords can you make with 4 digits? How many ways can 8 people sit in a row? How many ways can you choose a committee of 5 from 20 people?

Counting these by listing every possibility would take hours or years. Counting principles let us find these numbers in seconds using systematic reasoning.

These principles form the backbone of Probability (Class 10-12), Permutations and Combinations (Class 11), and are directly tested in JEE Main almost every year.

The Fundamental Principle of Counting

Also called the Multiplication Principle or the Basic Counting Principle.

Statement: If task A can be performed in $m$ ways, and after A is done, task B can be performed in $n$ ways, then the two tasks together can be performed in $m \times n$ ways.

Key condition: The tasks must be independent (the number of ways for B doesn’t depend on which way A was done).

Example: How many 2-digit numbers can be formed using digits 1–5 if repetition is allowed?

First digit: 5 choices (1, 2, 3, 4, or 5)
Second digit: 5 choices (independently)
Total: $5 \times 5 = 25$

Example (Without repetition): Same question, digits not repeated:

First digit: 5 choices
Second digit: only 4 remaining choices
Total: $5 \times 4 = 20$

This principle extends to any number of tasks: if tasks $T_1, T_2, \ldots, T_k$ can be done in $n_1, n_2, \ldots, n_k$ ways respectively, the total is $n_1 \times n_2 \times \cdots \times n_k$ .

The Addition Principle

Statement: If task A can be performed in $m$ ways and task B can be performed in $n$ ways, and the two tasks are mutually exclusive (cannot happen together), then either A or B can be performed in $m + n$ ways.

Example: From a group of 5 teachers and 8 students, choose 1 person as the representative. How many ways?

Choose a teacher: 5 ways
Choose a student: 8 ways
Total: $5 + 8 = 13$ ways

Multiplication vs Addition: Multiplication is for “AND” (both tasks), Addition is for “OR” (either task). This distinction is crucial.

Permutations

Permutation = arrangement where order matters.

P(n, r) = {^n}P_r = \frac{n!}{(n-r)!}

The number of ways to arrange $r$ objects chosen from $n$ distinct objects.

Example: How many 3-letter codes can be made from ABCDE (no repetition)?

P(5, 3) = \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{120}{2} = 60

Special case — All $n$ objects:

P(n, n) = n!

Arrangements of $n$ distinct objects = $n!$

Example: In how many ways can 6 people sit in a row?

6! = 720

Circular Permutations: Arrangements in a circle. Since rotations are identical, divide by $n$ :

\text{Circular arrangements of } n \text{ objects} = (n-1)!

Combinations

Combination = selection where order doesn’t matter.

C(n, r) = {^n}C_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}

Example: A committee of 3 from 6 people:

\binom{6}{3} = \frac{6!}{3! \cdot 3!} = 20

Key property: $\binom{n}{r} = \binom{n}{n-r}$ (choosing $r$ to include = choosing $n-r$ to exclude)

Example: $\binom{10}{7} = \binom{10}{3} = 120$ (much easier to calculate)

Permutations vs Combinations

Aspect	Permutation	Combination
Order	Matters	Doesn’t matter
Formula	$\frac{n!}{(n-r)!}$	$\frac{n!}{r!(n-r)!}$
Keyword	Arrange, rank, order	Select, choose, committee
Ratio	$P(n,r) = r! \times C(n,r)$	—

The Pigeonhole Principle

Statement: If $n + 1$ objects are distributed into $n$ boxes, then at least one box must contain at least 2 objects.

Generalised version: If $kn + 1$ objects are distributed into $n$ boxes, at least one box contains at least $k + 1$ objects.

Example 1: In any group of 367 people, at least two people share the same birthday (since there are only 366 possible birthdays).

Example 2: Among any 5 integers, at least two have the same remainder when divided by 4. (Since there are only 4 possible remainders: 0, 1, 2, 3.)

Example 3 (JEE level): Prove that among any 10 two-digit numbers, at least two have the same units digit.

Proof: Units digits can be 0–9 (10 possibilities). With 10 numbers and 10 possible units digits, by Pigeonhole, some units digit must repeat — or each digit appears exactly once (which also satisfies “at least” two having same digits in the limiting case of equality).

The Pigeonhole Principle seems obvious but it proves non-trivial results. In JEE, it appears as a proof or existence question.

Inclusion-Exclusion Principle

When counting elements in overlapping sets, we must avoid double-counting.

For two sets $A$ and $B$ :

|A \cup B| = |A| + |B| - |A \cap B|

For three sets $A$ , $B$ , $C$ :

|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|

Example: In a class of 40 students, 20 play cricket, 15 play football, and 8 play both. How many play at least one sport?

|C \cup F| = 20 + 15 - 8 = 27

How many play neither? $40 - 27 = 13$ .

Example (JEE Level): How many integers from 1 to 100 are divisible by 2, 3, or 5?

Let $A$ = multiples of 2, $B$ = multiples of 3, $C$ = multiples of 5.

$|A| = 50$ , $|B| = 33$ , $|C| = 20$

$|A \cap B \cap C|$ = multiples of 30 = 3

$|A \cup B \cup C| = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74$

Solved Examples

Easy — CBSE Class 11

Problem: How many 4-digit even numbers can be formed using 0, 1, 2, 3, 4, 5 (no repetition)?

Step 1: Units digit must be 0, 2, or 4 (to be even).

Case 1: Units digit = 0. Remaining 3 positions from 5 remaining digits. Thousands digit: 5 choices (not 0 ✓). Hundreds: 4. Tens: 3. Count: $5 \times 4 \times 3 = 60$

Case 2: Units digit = 2 or 4 (2 choices). Thousands digit: 4 choices (not 0, not the chosen even digit). Hundreds: 4. Tens: 3. Count: $2 \times 4 \times 4 \times 3 = 96$

Total: $60 + 96 = 156$

Medium — JEE Main Level

Problem: A committee of 5 is to be formed from 6 men and 4 women such that at least 2 women are on the committee. How many ways?

Cases with at least 2 women:

2 women, 3 men: $\binom{4}{2} \times \binom{6}{3} = 6 \times 20 = 120$
3 women, 2 men: $\binom{4}{3} \times \binom{6}{2} = 4 \times 15 = 60$
4 women, 1 man: $\binom{4}{4} \times \binom{6}{1} = 1 \times 6 = 6$

Total: $120 + 60 + 6 = 186$

Alternative (complementary counting): Total committees − (0 women) − (1 woman) = $\binom{10}{5} - \binom{4}{0}\binom{6}{5} - \binom{4}{1}\binom{6}{4} = 252 - 6 - 60 = 186$ . When “at least” conditions apply, always consider complementary counting — it’s often faster.

Hard — JEE Advanced Level

Problem: How many ways can the letters of “MISSISSIPPI” be arranged so that no two S’s are adjacent?

“MISSISSIPPI” has 11 letters: M×1, I×4, S×4, P×2.

Step 1: Arrange all letters except S’s: M, I, I, I, I, P, P (7 letters):

\frac{7!}{4! \cdot 2!} = \frac{5040}{48} = 105 \text{ arrangements}

Step 2: Choose 4 gaps from the 8 gaps (before, between, and after 7 arranged letters) for the 4 S’s:

\binom{8}{4} = 70

Total: $105 \times 70 = 7350$

Common Mistakes

Mistake 1: Multiplying when you should add. “Choose 1 book from shelf A OR 1 from shelf B” uses addition. “Choose 1 from A AND 1 from B” uses multiplication. The words OR/AND are your guide.

Mistake 2: Using combinations when order matters. “How many words can be formed?” — letters arranged in order → permutations. “How many teams?” — no ordering → combinations.

Mistake 3: Forgetting the restriction on 0 in leading position. For $k$ -digit numbers, the first digit cannot be 0 (else it becomes a $(k-1)$ -digit number). Always handle this separately.

Practice Questions

Q1. Find the number of 3-digit numbers formed using 1, 2, 3, 4, 5 with no repetition.

$5 \times 4 \times 3 = 60$

Q2. How many arrangements of “BANANA” are possible?

“BANANA” has 6 letters: B×1, A×3, N×2.

\frac{6!}{1! \cdot 3! \cdot 2!} = \frac{720}{12} = 60

Q3. In how many ways can 7 people sit around a circular table?

$(7-1)! = 6! = 720$

Q4. Among integers 1–50, how many are divisible by 4 or 6?

Multiples of 4 in 1–50: 12. Multiples of 6: 8. Multiples of LCM(4,6) = 12: 4.

$|4 \cup 6| = 12 + 8 - 4 = 16$

Q5. Prove that among any 5 integers, two will have the same remainder when divided by 4.

There are only 4 possible remainders when dividing by 4: 0, 1, 2, 3. By the Pigeonhole Principle, distributing 5 integers into 4 possible “remainder boxes” means at least one box contains at least 2 integers. Those two integers share the same remainder.

FAQs

Q: What’s the difference between $P(n,r)$ and $C(n,r)$ ? $P(n,r)$ counts ordered arrangements; $C(n,r)$ counts unordered selections. $P(n,r) = r! \times C(n,r)$ — to convert combinations to permutations, multiply by $r!$ (the number of orderings of the chosen $r$ items).

Q: When should I use complementary counting? When the condition says “at least $k$ ,” counting all valid cases directly can be tedious. Instead, count the complement (0, 1, …, $k-1$ cases) and subtract from the total. Usually faster.

Q: Is $0! = 1$ ? Why? Yes. By definition (or by the recurrence $n! = n \times (n-1)!$ , setting $n=1$ : $1! = 1 \times 0! \implies 0! = 1$ ). Practically, $\binom{n}{0} = \frac{n!}{0! \cdot n!} = 1$ , which makes sense — there’s exactly 1 way to choose nothing.

Q: How does Inclusion-Exclusion generalise? For $n$ sets, the pattern alternates: add single sets, subtract pairwise intersections, add triple intersections, and so on. The general formula has $2^n - 1$ terms. For most exam problems, two or three sets are sufficient.

Derangements — When Nothing Goes Right

A derangement is a permutation where no element appears in its original position. How many ways can $n$ letters be put into $n$ envelopes so that NO letter goes into the correct envelope?

D_n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!}\right)

For small values:

$D_1 = 0$ (one letter must go in its only envelope)
$D_2 = 1$ (swap the two)
$D_3 = 2$
$D_4 = 9$
$D_5 = 44$

Example (JEE Level): In how many ways can 4 married couples be seated in 4 chairs such that no one sits in the chair labelled with their partner’s name?

This is a derangement of 4 objects: $D_4 = 4!(1 - 1 + 1/2 - 1/6 + 1/24) = 24 \times (12/24 - 4/24 + 1/24) = 24 \times 9/24 = 9$ ways.

JEE Advanced has asked derangement problems disguised as “letter-envelope” or “hat-person” problems. The formula looks complex but for $n = 4$ or $n = 5$ , you can compute $D_n$ directly from the small values above. For $n \geq 6$ , use the recursion $D_n = (n-1)(D_{n-1} + D_{n-2})$ .

Stars and Bars — Distributing Identical Objects

How many ways can $n$ identical balls be placed into $k$ distinct boxes?

\binom{n + k - 1}{k - 1}

Example: Distribute 10 identical chocolates among 3 children.

\binom{10 + 3 - 1}{3 - 1} = \binom{12}{2} = 66

If each child must get at least one chocolate: give 1 to each first (leaving 7), then distribute 7 into 3 boxes: $\binom{7 + 2}{2} = \binom{9}{2} = 36$ .

Q6. In how many ways can we form a 5-digit number using digits 0-9 with repetition, such that the number is divisible by 5?

A number is divisible by 5 if its last digit is 0 or 5.

Case 1 (last digit = 0): First digit: 9 choices (1-9). Middle 3 digits: $10^3 = 1000$ each. Total: $9 \times 10^3 = 9000$ .

Case 2 (last digit = 5): First digit: 9 choices (1-9). Middle 3 digits: $10^3 = 1000$ . Total: $9 \times 10^3 = 9000$ .

Grand total: $9000 + 9000 = 18000$ .