Skip to content

Combinatorics: Counting, Pigeonhole and Derangements

CSIR NET algebra: permutations, combinations, stars and bars, surjections, pigeonhole principle, inclusion-exclusion and derangements with practice.

  • 8 min read
  • Updated
On this page · 16 sections
  1. Prerequisites
  2. The Hook: The Hat-Check Problem
  3. Counting Principles
  4. Permutations and Combinations
  5. Distributions: Balls into Boxes
  6. The Pigeonhole Principle
  7. Inclusion-Exclusion
  8. Derangements
  9. A Note on Recurrences
  10. Memory Tricks
  11. Don’t Confuse
  12. Common Mistakes
  13. Practice
  14. Quick Revision Table
  15. Key Takeaways
  16. What’s Next

Prerequisites

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

SituationCount
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.

BallsBoxesAny number per boxEach box non-empty (onto)At most one per box (one-one)
distinctdistinct\( k^n \)\( k!\,S(n, k) = \sum_{j=0}^{k}(-1)^j\binom{k}{j}(k-j)^n \)\( \frac{k!}{(k-n)!} \)
identicaldistinct\( \binom{n+k-1}{k-1} \)\( \binom{n-1}{k-1} \)\( \binom{k}{n} \)
distinctidentical\( \sum_{j=1}^{k} S(n, j) \)\( S(n, k) \)1 if \( n \le k \), else 0
identicalidenticalpartitions of \( n \) into at most \( k \) partspartitions of \( n \) into exactly \( k \) parts1 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 \)2345Bell \( B_n \)
\( n = 3 \)1315
\( n = 4 \)176115
\( n = 5 \)1152510152

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:

ClaimBoxes
Any \( n + 1 \) integers from \( \{1, \dots, 2n\} \) contain two consecutive (hence coprime) integersthe \( n \) pairs \( \{1,2\}, \{3,4\}, \dots, \{2n-1, 2n\} \)
Any \( n + 1 \) integers from \( \{1, \dots, 2n\} \) contain one dividing anotherwrite 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 strangersthe 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_{iThe number of elements in none of the sets is \( N - \lvert \bigcup A_i \rvert \), where \( N \) is the size of the universe. When the size of each \( k \)-fold intersection depends only on \( k \) (call it \( N_k \)), this collapses to

$$\#\{\text{in none}\} = \sum_{k=0}^{n} (-1)^k \binom{n}{k} N_k.$$

Three standard applications

  1. 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.
  2. 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 \).
  3. 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 \)12345678
\( D_n \)012944265185414833

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

ThisvsThat
\( 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

  1. Find \( D_5 \).
  2. How many solutions does \( x + y + z = 10 \) have in non-negative integers?
  3. What is the least number of integers you must pick to be sure two of them have the same remainder mod 7?
Answers
  1. 44. \( 5!\left(\frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}\right) = 60 - 20 + 5 - 1 = 44 \).
  2. 66. \( \binom{10 + 2}{2} = \binom{12}{2} = 66 \).
  3. 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

IdeaFact
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 \)-setBell \( 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-exclusionsingles \( - \) 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