Combinatorics: Counting, Pigeonhole and Derangements
CSIR NET algebra: permutations, combinations, stars and bars, surjections, pigeonhole principle, inclusion-exclusion and derangements with practice.
- 8 min
On this page · 16 sections
Prerequisites
- Counting, Probability and Number Properties: the Part A version of \( {}^nP_r \) and \( {}^nC_r \). This page assumes it and goes further.
- Real Numbers, Sets and Countability: counting by bijection is the finite case of the same idea.
- Comfort with \( \binom{n}{r} \), factorials and finite sums.
The Hook: The Hat-Check Problem
Counting Principles
Multiplication principle. A task done in two stages, with \( m \) ways for the first and \( n \) ways for the second whatever the first was, can be done in \( mn \) ways.
Addition principle. If a choice is of type A (\( m \) ways) or type B (\( n \) ways) and no choice is of both types, there are \( m + n \) ways.
Bijection principle. If there is a bijection between two finite sets, they have the same size. Most clever counts (stars and bars, lattice paths, Catalan numbers) are a bijection in disguise.
Double counting. Count one set in two ways and equate the results. The identity \( \sum_k k\binom{n}{k} = n2^{n-1} \) counts pairs (committee, chair) either by committee size or by choosing the chair first.
Permutations and Combinations
| Situation | Count |
|---|---|
| Ordered selection of \( r \) from \( n \) distinct objects, no repetition | \( {}^nP_r = \frac{n!}{(n-r)!} \) |
| Ordered selection with repetition allowed | \( n^r \) |
| Unordered selection of \( r \) from \( n \), no repetition | \( \binom{n}{r} = \frac{n!}{r!\,(n-r)!} \) |
| Unordered selection with repetition (multisets of size \( r \) from \( n \) types) | \( \binom{n+r-1}{r} \) |
| Arrangements of \( n \) objects with \( n_1, \dots, n_k \) alike | \( \frac{n!}{n_1!\,n_2!\cdots n_k!} \) (multinomial) |
| \( n \) distinct objects in a circle | \( (n-1)! \) |
| \( n \) distinct beads on a necklace (flip allowed), \( n \ge 3 \) | \( \frac{(n-1)!}{2} \) |
Binomial identities worth knowing cold
$$\sum_{k=0}^{n}\binom{n}{k} = 2^n, \qquad \sum_{k=0}^{n}(-1)^k\binom{n}{k} = 0 \ (n \ge 1), \qquad \sum_{k=0}^{n} k\binom{n}{k} = n2^{n-1}$$$$\underbrace{\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}}_{\text{Pascal}}, \qquad \underbrace{\sum_{k}\binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}}_{\text{Vandermonde}}, \qquad \underbrace{\sum_{i=r}^{n}\binom{i}{r} = \binom{n+1}{r+1}}_{\text{hockey stick}}$$Also \( \sum_k \binom{n}{k}^2 = \binom{2n}{n} \) (Vandermonde with \( m = n = r \)), and the number of subsets of an \( n \)-set with an even number of elements is \( 2^{n-1} \) for \( n \ge 1 \).
Stars and bars
The number of solutions of \( x_1 + x_2 + \dots + x_k = n \) in integers:
$$\boxed{x_i \ge 0: \ \binom{n+k-1}{k-1}} \qquad \boxed{x_i \ge 1: \ \binom{n-1}{k-1}}$$Proof: a solution with \( x_i \ge 0 \) is a row of \( n \) stars and \( k - 1 \) bars; choose the bar positions. Lower bounds \( x_i \ge a_i \) are handled by substituting \( y_i = x_i - a_i \). Upper bounds need inclusion-exclusion (below).
Choosing without neighbours. The number of \( r \)-subsets of \( \{1, \dots, n\} \) with no two consecutive elements is \( \binom{n-r+1}{r} \): subtract \( 0, 1, \dots, r-1 \) from the chosen elements in increasing order to get an arbitrary \( r \)-subset of \( \{1, \dots, n-r+1\} \).
Distributions: Balls into Boxes
This table decides most distribution questions. \( n \) balls, \( k \) boxes.
| Balls | Boxes | Any number per box | Each box non-empty (onto) | At most one per box (one-one) |
|---|---|---|---|---|
| distinct | distinct | \( k^n \) | \( k!\,S(n, k) = \sum_{j=0}^{k}(-1)^j\binom{k}{j}(k-j)^n \) | \( \frac{k!}{(k-n)!} \) |
| identical | distinct | \( \binom{n+k-1}{k-1} \) | \( \binom{n-1}{k-1} \) | \( \binom{k}{n} \) |
| distinct | identical | \( \sum_{j=1}^{k} S(n, j) \) | \( S(n, k) \) | 1 if \( n \le k \), else 0 |
| identical | identical | partitions of \( n \) into at most \( k \) parts | partitions of \( n \) into exactly \( k \) parts | 1 if \( n \le k \), else 0 |
Here \( S(n, k) \) is the Stirling number of the second kind: the number of partitions of an \( n \)-set into \( k \) non-empty blocks. It satisfies \( S(n, k) = kS(n-1, k) + S(n-1, k-1) \), with \( S(n, 1) = S(n, n) = 1 \) and \( S(n, 2) = 2^{n-1} - 1 \).
| \( S(n,k) \) | \( k=1 \) | 2 | 3 | 4 | 5 | Bell \( B_n \) |
|---|---|---|---|---|---|---|
| \( n = 3 \) | 1 | 3 | 1 | 5 | ||
| \( n = 4 \) | 1 | 7 | 6 | 1 | 15 | |
| \( n = 5 \) | 1 | 15 | 25 | 10 | 1 | 52 |
The Bell number \( B_n = \sum_k S(n, k) \) counts all partitions of an \( n \)-set, which is also the number of equivalence relations on an \( n \)-set: \( B_3 = 5 \), \( B_4 = 15 \).
In the language of functions from an \( n \)-set to a \( k \)-set: there are \( k^n \) functions, \( \frac{k!}{(k-n)!} \) injections and \( k!\,S(n,k) \) surjections.
Catalan numbers
$$\boxed{C_n = \frac{1}{n+1}\binom{2n}{n}}: \quad 1, 1, 2, 5, 14, 42, 132, \dots \ (n = 0, 1, 2, \dots)$$\( C_n \) counts lattice paths from \( (0,0) \) to \( (n,n) \) with unit right and up steps that never go above the diagonal, balanced strings of \( n \) pairs of brackets, full binary trees with \( n + 1 \) leaves, and triangulations of a convex \( (n+2) \)-gon. The count of all lattice paths to \( (n, n) \) is \( \binom{2n}{n} \); the reflection principle removes the \( \binom{2n}{n+1} \) bad ones.
The Pigeonhole Principle
The art is choosing the boxes. Standard choices:
| Claim | Boxes |
|---|---|
| Any \( n + 1 \) integers from \( \{1, \dots, 2n\} \) contain two consecutive (hence coprime) integers | the \( n \) pairs \( \{1,2\}, \{3,4\}, \dots, \{2n-1, 2n\} \) |
| Any \( n + 1 \) integers from \( \{1, \dots, 2n\} \) contain one dividing another | write each as \( 2^a m \), \( m \) odd; box = odd part \( m \) (\( n \) choices) |
| Any \( n + 1 \) integers contain two with the same remainder mod \( n \) | the \( n \) residue classes |
| Among any \( n \) integers, some non-empty block of consecutive ones has sum divisible by \( n \) | the remainders of the \( n \) partial sums \( s_1, \dots, s_n \); if none is 0 mod \( n \), two are equal and their difference works |
| 5 points in a unit square: two within distance \( \frac{\sqrt{2}}{2} \) | the four half-size squares |
| Any sequence of \( mn + 1 \) distinct reals has an increasing subsequence of length \( m + 1 \) or a decreasing one of length \( n + 1 \) (Erdős–Szekeres) | label each term by the length of the longest increasing subsequence starting there |
| In any group of 6 people, 3 know each other or 3 are mutual strangers | the 5 edges at one vertex, in 2 colours: 3 have the same colour |
Pigeonhole also proves algebraic facts you will meet later on this chapter: in a finite group, the powers \( a, a^2, a^3, \dots \) must repeat, so every element has finite order; a finite integral domain is a field because \( x \mapsto ax \) is injective on a finite set, hence onto.
Inclusion-Exclusion
For finite sets \( A_1, \dots, A_n \):
$$\boxed{\left\lvert \bigcup_{i=1}^{n} A_i \right\rvert = \sum_i \lvert A_i \rvert - \sum_{iThree standard applications
- Euler’s phi. If \( n = p_1^{a_1}\cdots p_r^{a_r} \), let \( A_i \) be the multiples of \( p_i \) in \( \{1, \dots, n\} \). Inclusion-exclusion gives \( \varphi(n) = n\prod_i \left(1 - \frac{1}{p_i}\right) \). The number-theory page builds on this.
- Surjections. Let \( A_i \) be the functions \( [n] \to [k] \) that miss value \( i \). Then the number of onto functions is \( \sum_{j=0}^{k} (-1)^j \binom{k}{j}(k - j)^n \). For \( n = 5 \), \( k = 3 \): \( 243 - 3 \cdot 32 + 3 \cdot 1 = 150 \).
- Upper bounds in stars and bars. The number of solutions of \( x_1 + \dots + x_k = n \), \( 0 \le x_i \le c \), is \( \sum_j (-1)^j \binom{k}{j}\binom{n - j(c+1) + k - 1}{k - 1} \), the sum running while \( n - j(c+1) \ge 0 \).
Derangements
A derangement of \( \{1, \dots, n\} \) is a permutation with no fixed point. Let \( A_i \) be the permutations fixing \( i \); a \( k \)-fold intersection has \( (n-k)! \) elements. Inclusion-exclusion gives
$$\boxed{D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \dots + \frac{(-1)^n}{n!}\right)}$$| \( n \) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| \( D_n \) | 0 | 1 | 2 | 9 | 44 | 265 | 1854 | 14833 |
Recurrences (with \( D_0 = 1 \), \( D_1 = 0 \)):
$$D_n = (n-1)\left(D_{n-1} + D_{n-2}\right), \qquad D_n = nD_{n-1} + (-1)^n.$$The first has a direct proof: in a derangement, \( n \) goes to some \( i \ne n \) (\( n - 1 \) choices); either \( i \) goes back to \( n \) (the rest is a derangement of \( n - 2 \) objects) or it does not (a derangement of \( n - 1 \) objects after renaming).
Consequences
- \( D_n \) is the nearest integer to \( \frac{n!}{e} \) for \( n \ge 1 \), and \( \frac{D_n}{n!} \to \frac{1}{e} \approx 0.3679 \). The ratio oscillates around \( \frac{1}{e} \) (0.5, 0.333, 0.375, 0.367, …); it is not monotone.
- From \( D_n = nD_{n-1} + (-1)^n \): \( D_n \) is odd exactly when \( n \) is even.
- Exactly \( k \) fixed points: choose the fixed points, derange the rest: \( \binom{n}{k}D_{n-k} \). Summing over \( k \) gives \( n! \).
- At least one fixed point: \( n! - D_n \).
A Note on Recurrences
Many counting questions reduce to a linear recurrence. The number \( a_n \) of binary strings of length \( n \) with no two consecutive 1s satisfies \( a_n = a_{n-1} + a_{n-2} \) (the string ends in 0, or in 01), with \( a_1 = 2 \), \( a_2 = 3 \). So \( a_n = F_{n+2} \), a Fibonacci number: 2, 3, 5, 8, 13, 21, 34, …
For \( a_n = c_1 a_{n-1} + c_2 a_{n-2} \), solve the characteristic equation \( x^2 = c_1 x + c_2 \). Distinct roots \( r_1, r_2 \) give \( a_n = \alpha r_1^n + \beta r_2^n \); a repeated root \( r \) gives \( a_n = (\alpha + \beta n)r^n \). Fix \( \alpha, \beta \) from the initial values.
graph TD
Q[Counting question] --> O{Does order matter?}
O -->|yes| R{Repetition allowed?}
O -->|no| S{Repetition allowed?}
R -->|yes| A1["n to the power r"]
R -->|no| A2["nPr"]
S -->|yes| A3["stars and bars C(n+r-1, r)"]
S -->|no| A4["nCr"]
Q --> F{Forbidden positions or 'none of'?}
F -->|yes| IE[Inclusion-exclusion / derangements]
Q --> E{Only need existence?}
E -->|yes| PH[Pigeonhole: choose the boxes]Memory Tricks
Don’t Confuse
| This | vs | That |
|---|---|---|
| \( k^n \): functions from an \( n \)-set to a \( k \)-set | \( n^k \): functions from a \( k \)-set to an \( n \)-set | |
| \( \binom{n+k-1}{k-1} \): solutions with \( x_i \ge 0 \) | \( \binom{n-1}{k-1} \): solutions with \( x_i \ge 1 \) | |
| \( S(n, k) \): partitions into \( k \) blocks (boxes identical) | \( k!\,S(n, k) \): surjections (boxes distinct) | |
| \( D_n \): no fixed point | \( n! - D_n \): at least one fixed point | |
| \( \binom{n}{k}D_{n-k} \): exactly \( k \) fixed | \( \binom{n}{k}(n-k)! \): at least these \( k \) fixed (overcounts “at least \( k \)”) | |
| \( (n-1)! \): seats round a table | \( \frac{(n-1)!}{2} \): necklace that can be flipped |
Common Mistakes
Practice
All questions below are original practice questions written for this page. They are not from any CSIR NET paper. In Level 3, as in Part C, one or more options may be correct.
Level 1: Foundation
- Find \( D_5 \).
- How many solutions does \( x + y + z = 10 \) have in non-negative integers?
- What is the least number of integers you must pick to be sure two of them have the same remainder mod 7?
Answers
- 44. \( 5!\left(\frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}\right) = 60 - 20 + 5 - 1 = 44 \).
- 66. \( \binom{10 + 2}{2} = \binom{12}{2} = 66 \).
- 8. There are 7 residue classes; 7 integers can all be different mod 7, the eighth must repeat one.
Level 2: Part B Style
Practice Q1. The number of integers in \( \{1, 2, \dots, 1000\} \) divisible by none of 2, 3, 5 is:
(a) 266 (b) 267 (c) 734 (d) 334
Answer: (a)
By inclusion-exclusion (worked above): \( 1000 - (1033 - 332 + 33) = 266 \). Option (c) is the count divisible by at least one. As a check, \( \varphi(30) = 8 \) residues per block of 30, \( 33 \times 8 = 264 \), plus 991 and 997 in the last partial block \( 991, \dots, 1000 \): 266.
Practice Q2. The number of onto functions from a 5-element set to a 3-element set is:
(a) 243 (b) 150 (c) 60 (d) 25
Answer: (b)
\( 3^5 - \binom{3}{1}2^5 + \binom{3}{2}1^5 = 243 - 96 + 3 = 150 \). Equivalently \( 3!\,S(5, 3) = 6 \times 25 \). Option (d) is \( S(5, 3) \) itself: the number of ways to split the 5-set into 3 unlabelled blocks.
Practice Q3. The number of permutations of \( \{1, 2, \dots, 6\} \) with exactly two fixed points is:
(a) 135 (b) 120 (c) 265 (d) 90
Answer: (a)
Choose the two fixed points, \( \binom{6}{2} = 15 \), and derange the other four, \( D_4 = 9 \): \( 15 \times 9 = 135 \).
Practice Q4. The number of 3-element subsets of \( \{1, 2, \dots, 20\} \) containing no two consecutive integers is:
(a) 1140 (b) 816 (c) 969 (d) 680
Answer: (b)
\( \binom{n - r + 1}{r} = \binom{18}{3} = 816 \). Map \( a < b < c \) to \( a < b - 1 < c - 2 \), an arbitrary 3-subset of \( \{1, \dots, 18\} \). Option (a) is \( \binom{20}{3} \), all 3-subsets.
Level 3: Part C Style
Practice Q5. Let \( D_n \) denote the number of derangements of \( \{1, \dots, n\} \). Which of the following are true?
(a) \( D_n = nD_{n-1} + (-1)^n \) for all \( n \ge 2 \). (b) \( D_6 = 265 \). (c) \( \frac{D_n}{n!} \) is a decreasing function of \( n \) for \( n \ge 2 \). (d) \( D_n \) is odd if and only if \( n \) is even.
Answer: (a), (b) and (d)
- (a) True. From the formula, \( D_n - nD_{n-1} = n!\frac{(-1)^n}{n!} = (-1)^n \): every term of \( D_n \) except the last matches a term of \( nD_{n-1} \).
- (b) True. \( D_6 = 6D_5 + 1 = 6 \times 44 + 1 = 265 \).
- (c) False. \( \frac{D_2}{2!} = 0.5 \), \( \frac{D_3}{3!} = 0.333 \), \( \frac{D_4}{4!} = 0.375 \): it goes up again. The partial sums of an alternating series oscillate about the limit \( \frac{1}{e} \).
- (d) True. By (a), \( D_n \equiv nD_{n-1} + (-1)^n \equiv nD_{n-1} + 1 \pmod 2 \). For even \( n \), \( D_n \equiv 1 \). For odd \( n \), \( D_n \equiv D_{n-1} + 1 \equiv 1 + 1 = 0 \) (as \( n - 1 \) is even). Base case \( D_2 = 1 \).
Practice Q6. Let \( S \) be any subset of \( \{1, 2, \dots, 100\} \) with 51 elements. Which of the following must be true?
(a) \( S \) contains two consecutive integers. (b) \( S \) contains two distinct elements, one of which divides the other. (c) \( S \) contains two elements whose sum is 101. (d) \( S \) contains two elements whose difference is 51.
Answer: (a), (b) and (c)
- (a) True. Boxes \( \{1, 2\}, \{3, 4\}, \dots, \{99, 100\} \): 50 boxes, 51 elements.
- (b) True. Write each element as \( 2^a m \) with \( m \) odd; \( m \in \{1, 3, \dots, 99\} \), 50 values. Two elements share \( m \), and the one with smaller power of 2 divides the other.
- (c) True. Boxes \( \{k, 101 - k\} \) for \( k = 1, \dots, 50 \) partition \( \{1, \dots, 100\} \) into 50 pairs.
- (d) False. \( S = \{1, 2, \dots, 51\} \) has largest difference 50. (The pairs \( \{k, k+51\} \), \( k \le 49 \), leave 50 and 51 unpaired, so pigeonhole does not apply.)
Practice Q7. Let \( a_n \) be the number of binary strings of length \( n \) with no two consecutive 1s. Which of the following are true?
(a) \( a_n = a_{n-1} + a_{n-2} \) for \( n \ge 3 \). (b) \( a_5 = 13 \). (c) \( a_6 = 20 \). (d) \( a_n \) equals the number of subsets of \( \{1, \dots, n\} \) with no two consecutive elements.
Answer: (a), (b) and (d)
- (a) True. A valid string ends in 0 (any valid string of length \( n - 1 \) before it) or in 01 (any valid string of length \( n - 2 \) before it).
- (b) True. \( a_1 = 2 \), \( a_2 = 3 \), \( a_3 = 5 \), \( a_4 = 8 \), \( a_5 = 13 \).
- (c) False. \( a_6 = 8 + 13 = 21 \).
- (d) True. A subset corresponds to its indicator string; “no two consecutive elements” is “no 11”. Summing \( \binom{n-r+1}{r} \) over \( r \) gives the same Fibonacci numbers.
Quick Revision Table
| Idea | Fact |
|---|---|
| Multisets of size \( r \) from \( n \) types | \( \binom{n+r-1}{r} \) |
| \( x_1 + \dots + x_k = n \) | \( \binom{n+k-1}{k-1} \) (\( \ge 0 \)); \( \binom{n-1}{k-1} \) (\( \ge 1 \)) |
| \( r \)-subsets with no two consecutive | \( \binom{n-r+1}{r} \) |
| Surjections \( [n] \to [k] \) | \( \sum_j (-1)^j\binom{k}{j}(k-j)^n = k!\,S(n,k) \) |
| Equivalence relations on \( n \)-set | Bell \( B_n \): 1, 2, 5, 15, 52, 203 |
| Catalan | \( \frac{1}{n+1}\binom{2n}{n} \): 1, 1, 2, 5, 14, 42 |
| Pigeonhole | \( n \) objects, \( k \) boxes \( \Rightarrow \) some box has \( \ge \lceil n/k \rceil \) |
| Inclusion-exclusion | singles \( - \) pairs \( + \) triples \( - \dots \) |
| Derangements | \( D_n = n!\sum (-1)^k/k! \approx n!/e \); 0, 1, 2, 9, 44, 265, 1854 |
| Recurrences | \( D_n = (n-1)(D_{n-1} + D_{n-2}) = nD_{n-1} + (-1)^n \) |
| Exactly \( k \) fixed points | \( \binom{n}{k}D_{n-k} \) |
Key Takeaways
What’s Next
- Number Theory: Congruences, CRT and Primitive Roots: inclusion-exclusion becomes Euler’s \( \varphi \), and pigeonhole becomes the order of an element mod \( n \).
- Groups, Subgroups and Homomorphisms: derangements reappear as fixed-point-free permutations in \( S_n \), and cycle types are counted with the formulas above.
- Group Actions, Class Equation and Sylow Theorems: Burnside’s lemma counts necklaces up to symmetry.
- Algebra: Quick Revision.