5.1 Counting: Pigeonhole, Inclusion–Exclusion, Derangements
Counting without listing: permutations and combinations, the binomial and multinomial theorems, stars and bars, the pigeonhole principle, inclusion–exclusion, derangements, surjections, Stirling numbers and the number of relations on a finite set.
How many ways can six people draw names for a gift exchange so that nobody draws their own name? How many relations on a four-element set are antisymmetric? How many integers up to $2100$ are divisible by none of $3$, $5$, $7$? Listing is hopeless even for questions of this modest size, and guessing is dangerous — the two most common errors in counting, counting something twice and confusing ordered with unordered choices, both produce plausible-looking numbers. This section builds a small toolkit that answers such questions exactly and, just as importantly, proves that the answers are right: the sum and product rules, bijections, double counting, the pigeonhole principle and the principle of inclusion–exclusion.
Counting is not an isolated topic in the syllabus. Lagrange's theorem, the class equation and the Sylow theorems of Chapter 6 are counting arguments; the number of irreducible polynomials over a finite field (Chapter 8) is computed by inclusion–exclusion; Euler's $\varphi$-function (§5.3) is inclusion–exclusion over the prime divisors of $n$; and every discrete probability in Unit 4 is a ratio of two counts. In CSIR NET the topic appears directly in Part B as a short computation (derangements, surjections, relations, integer solutions with bounds, the least number that forces a repetition) and in Part C as a list of counting claims in which the wrong options are the classical mistakes collected in the ⚠️ box below.
Counting Principles, Permutations and Combinations
Throughout, $[n]=\{1,2,\dots,n\}$ (with $[0]=\varnothing$) and $|A|$ is the number of elements of a finite set $A$. Every counting argument in this section is built from five elementary principles.
Let $A$, $B$ be finite sets.
- Sum rule. If $A\cap B=\varnothing$ then $|A\cup B|=|A|+|B|$; in general $|A\cup B|=|A|+|B|-|A\cap B|$.
- Product rule. $|A\times B|=|A|\,|B|$. More generally, if each object of a set $\mathcal{O}$ is produced by a sequence of $k$ choices, the $i$-th choice can be made in $m_i$ ways whatever the earlier choices were (the options may depend on earlier choices, their number may not), and different choice sequences produce different objects, then $|\mathcal{O}|=m_1m_2\cdots m_k$.
- Bijection rule. If there is a bijection $A\to B$ then $|A|=|B|$.
- Division rule. If $f:A\to B$ is surjective and every fibre $f^{-1}(b)$ has exactly $d$ elements, then $|A|=d\,|B|$.
- Double counting. For any relation $R\subseteq A\times B$, $\ |R|=\sum_{a\in A}|\{b:(a,b)\in R\}|$ and also $|R|=\sum_{b\in B}|\{a:(a,b)\in R\}|$.
Proof. (1) Listing the elements of $A$ followed by those of $B$ lists $A\cup B$ without repetition when the sets are disjoint. In general $A\cup B$ is the disjoint union of $A$ and $B\setminus A$, and $B$ is the disjoint union of $B\setminus A$ and $A\cap B$, so $|A\cup B|=|A|+|B|-|A\cap B|$. (2) $A\times B=\bigcup_{a\in A}\{a\}\times B$ is a disjoint union of $|A|$ sets of size $|B|$; apply (1) repeatedly. For $k$ stages use induction on $k$: group the objects according to the first $k-1$ choices; by induction there are $m_1\cdots m_{k-1}$ groups, each group contains exactly $m_k$ objects, and distinct groups are disjoint. (3) A bijection pairs off the elements. (4) $A$ is the disjoint union of the $|B|$ fibres, each of size $d$. (5) Partition $R$ according to the first coordinate of its pairs, or according to the second, and apply (1). ∎
Double counting is deceptively powerful. Applied to the relation "vertex $v$ lies on edge $e$" in a finite graph it gives the handshake lemma $\sum_v\deg v=2|E|$; applied to "element $g$ lies in coset $C$" it will give Lagrange's theorem in Chapter 6.
For integers $n\ge0$ and $k\ge0$ let $n!=1\cdot2\cdots n$ ($0!=1$) and let $n^{\underline{k}}=n(n-1)\cdots(n-k+1)$ be the falling factorial ($k$ factors; $n^{\underline 0}=1$, and $n^{\underline{k}}=0$ if $k\gt n$).
- A $k$-permutation of an $n$-set $X$ is a sequence $(x_1,\dots,x_k)$ of $k$ distinct elements of $X$ (an ordered selection without repetition). An $n$-permutation of $X$ is simply a permutation, i.e. a bijection $X\to X$ written as the list of its values.
- A $k$-combination of $X$ is a $k$-element subset of $X$ (an unordered selection without repetition). The number of $k$-subsets of an $n$-set is denoted $\binom{n}{k}$, the binomial coefficient; $\binom nk=0$ if $k\gt n$.
Let $0\le k\le n$.
- An $n$-set has $n^{\underline k}=\dfrac{n!}{(n-k)!}$ $k$-permutations and $n!$ permutations. There are $n^k$ functions $[k]\to[n]$, of which $n^{\underline k}$ are injective.
- $\displaystyle\binom nk=\frac{n^{\underline k}}{k!}=\frac{n!}{k!\,(n-k)!}$.
- Circular arrangements. The number of ways to seat $n\ge1$ distinct people round a circular table, two seatings being the same when one is a rotation of the other, is $(n-1)!$. If reflections are also identified (beads on a ring that can be turned over) and $n\ge3$, the number is $\tfrac12(n-1)!$.
Proof. (1) The first entry of a $k$-permutation can be chosen in $n$ ways, the second in $n-1$ ways (any element except the first), …, the $k$-th in $n-k+1$ ways; the product rule gives $n^{\underline k}$. A function $[k]\to[n]$ is a choice of $f(1),\dots,f(k)$, each in $n$ ways; it is injective exactly when $(f(1),\dots,f(k))$ is a $k$-permutation of $[n]$.
(2) "Forget the order" maps the set of $k$-permutations onto the set of $k$-subsets, and the fibre over a $k$-subset $S$ consists of the $k!$ orderings of $S$. By the division rule $n^{\underline k}=k!\binom nk$.
(3) Seat the people and read their names clockwise starting from any one of the $n$ seats: each circular seating gives exactly $n$ different linear arrangements (the $n$ starting points give different lists because the people are distinct), and every linear arrangement arises from exactly one circular seating. By the division rule there are $n!/n=(n-1)!$ seatings. Turning a ring over replaces each arrangement by its mirror image. For $n\ge3$ the two differ: fix a person $P$; in one the clockwise neighbour of $P$ is some $Q$, in the mirror image it is $P$'s anticlockwise neighbour, which is a different person $Q'\ne Q$. So the rotation classes pair off into classes of size exactly $2$, and there are $\tfrac12(n-1)!$ of them. ∎
Proof. Write $(x+y)^n=(x+y)(x+y)\cdots(x+y)$ with $n$ factors and expand by the distributive law: the result is the sum of all $2^n$ words $w_1w_2\cdots w_n$ in which $w_i\in\{x,y\}$ is the term taken from the $i$-th factor. Because $x$ and $y$ commute, a word containing exactly $k$ letters $x$ equals $x^ky^{n-k}$, and such a word is determined by the set of positions of its $x$'s, a $k$-subset of $[n]$. There are $\binom nk$ of them, which is the coefficient of $x^ky^{n-k}$. Putting $x=y=1$ and $x=-1$, $y=1$ gives the two sums ($0^n=0$ for $n\ge1$). ∎
The two sums have combinatorial meanings: $2^n=|\mathcal{P}([n])|$, and the alternating sum says that an $n$-set with $n\ge1$ has as many subsets of even size as of odd size, namely $2^{n-1}$ each. Commutativity cannot be dropped: for $2\times2$ matrices with $AB\ne BA$, $(A+B)^2=A^2+AB+BA+B^2$, which is not $A^2+2AB+B^2$.
For integers $n,m,k\ge0$ (with $\binom ab=0$ when $b\lt0$ or $b\gt a$):
Proof. Each identity counts one set in two ways. Symmetry: $S\mapsto[n]\setminus S$ is a bijection from $k$-subsets to $(n-k)$-subsets. Pascal: a $k$-subset of $[n]$ either contains $n$ — and is then $\{n\}$ together with a $(k-1)$-subset of $[n-1]$ — or is a $k$-subset of $[n-1]$. Absorption: count pairs $(S,c)$ with $S\subseteq[n]$, $|S|=k$, $c\in S$ (a committee with a chair): choosing $S$ first gives $k\binom nk$, choosing the chair first and then the other $k-1$ members gives $n\binom{n-1}{k-1}$. Vandermonde: from $m$ red and $n$ blue balls, a $k$-subset with exactly $j$ red balls can be chosen in $\binom mj\binom n{k-j}$ ways; sum over $j$. Hockey stick: classify the $(k+1)$-subsets of $[n+1]$ by their largest element $i+1$ (where $k\le i\le n$); the other $k$ elements form a $k$-subset of $[i]$. ∎
Selecting $k$ objects from $n$ kinds: ask two questions — does order matter? may a kind be repeated?
| no repetition | repetition allowed | |
|---|---|---|
| ordered | $n^{\underline k}=\frac{n!}{(n-k)!}$ (injections) | $n^k$ (all functions $[k]\to[n]$) |
| unordered | $\binom nk$ (subsets) | $\binom{n+k-1}{k}$ (multisets, Theorem 5.6) |
Then: (i) restrictions — place the restricted objects first ("glue" objects that must be together into one block; put objects that must be apart into the gaps between the others); (ii) "at least one" — count the complement ("none") and subtract; (iii) check for double counting — if the same object can be produced by two different choice sequences, the product rule does not apply as it stands; (iv) sanity-check a small case by listing.
Repetition: Multisets, Multinomials and Stars and Bars
When objects of the same kind are indistinguishable — letters of a word, identical coins, scoops of the same flavour — we need counts of arrangements of multisets and of selections with repetition. Both reduce to binomial coefficients by a clever bijection.
A multiset on a set $X$ is a function $m:X\to\{0,1,2,\dots\}$ ($m(x)$ is the multiplicity of $x$); its size is $\sum_xm(x)$. For integers $k_1,\dots,k_r\ge0$ with $k_1+\cdots+k_r=n$ the multinomial coefficient is $$\binom{n}{k_1,k_2,\dots,k_r}=\frac{n!}{k_1!\,k_2!\cdots k_r!}.$$ For $r=2$ it is the binomial coefficient: $\binom{n}{k,\,n-k}=\binom nk$.
- The number of distinct words of length $n$ containing exactly $k_i$ copies of letter $i$ ($i=1,\dots,r$, $\sum k_i=n$) is $\binom{n}{k_1,\dots,k_r}$. The same number counts the ways to place $n$ distinct objects into $r$ labelled boxes so that box $i$ receives exactly $k_i$ objects, and it equals $\binom n{k_1}\binom{n-k_1}{k_2}\cdots\binom{k_r}{k_r}$.
- Multinomial theorem. For commuting $x_1,\dots,x_r$ and $n\ge0$, $$(x_1+\cdots+x_r)^n=\sum_{\substack{k_1+\cdots+k_r=n\\ k_i\ge0}}\binom{n}{k_1,\dots,k_r}x_1^{k_1}\cdots x_r^{k_r}.$$
Proof. (1) Attach labels to the copies (I$_1$, I$_2$, I$_3$, I$_4$, …) so that all $n$ letters are distinct; there are $n!$ labelled words. Erasing the labels maps labelled words onto unlabelled ones, and the fibre over a word consists of the $k_1!\cdots k_r!$ ways to permute the labels within each letter. The division rule gives $n!=k_1!\cdots k_r!\cdot(\text{number of words})$. A word $w_1\cdots w_n$ corresponds to the distribution "object $j$ goes into box $w_j$", which is a bijection between words and distributions with $k_i$ objects in box $i$. Choosing first the $k_1$ positions of letter $1$, then $k_2$ of the remaining $n-k_1$ positions, and so on, gives the product of binomials (and the product telescopes to $n!/(k_1!\cdots k_r!)$). (2) As in the binomial theorem, expanding the product gives all $r^n$ words in $x_1,\dots,x_r$; by commutativity a word with $k_i$ letters $x_i$ equals $x_1^{k_1}\cdots x_r^{k_r}$, and by (1) there are $\binom{n}{k_1,\dots,k_r}$ such words. ∎
Let $n\ge0$ and $r\ge1$ be integers.
- The equation $x_1+x_2+\cdots+x_r=n$ has exactly $\displaystyle\binom{n+r-1}{r-1}$ solutions in nonnegative integers.
- For $n\ge1$ it has exactly $\displaystyle\binom{n-1}{r-1}$ solutions in positive integers.
- The number of $k$-element multisets on an $n$-set (selections of $k$ objects from $n$ kinds, repetition allowed, order irrelevant) is $\displaystyle\binom{n+k-1}{k}$; this is also the number of non-decreasing functions $[k]\to[n]$. The number of strictly increasing functions $[k]\to[n]$ is $\binom nk$.
- The inequality $x_1+\cdots+x_r\le n$ has $\displaystyle\binom{n+r}{r}$ solutions in nonnegative integers.
Proof. (1) Encode a solution $(x_1,\dots,x_r)$ as a row of $n$ stars and $r-1$ bars: $x_1$ stars, a bar, $x_2$ stars, a bar, …, a bar, $x_r$ stars. For example, with $n=7$, $r=4$, the solution $(2,0,4,1)$ becomes $\star\star\,|\,|\,\star\star\star\star\,|\,\star$. Conversely every row of $n$ stars and $r-1$ bars decodes to a solution: $x_1$ is the number of stars before the first bar, $x_i$ the number between the $(i-1)$-st and $i$-th bars, $x_r$ the number after the last bar. These maps are inverse to each other, so solutions correspond bijectively to rows, and a row is determined by choosing which $r-1$ of its $n+r-1$ places carry bars.
(2) Put $y_i=x_i-1$: positive solutions of $\sum x_i=n$ correspond bijectively to nonnegative solutions of $\sum y_i=n-r$, of which there are $\binom{n-r+r-1}{r-1}=\binom{n-1}{r-1}$ (zero if $n\lt r$). Directly: write $n$ stars in a row and put $r-1$ bars into the $n-1$ gaps between consecutive stars, at most one per gap.
(3) A $k$-multiset on $\{a_1,\dots,a_n\}$ is the same as a solution of $m_1+\cdots+m_n=k$ in nonnegative integers ($m_i$ = multiplicity of $a_i$), so by (1) there are $\binom{k+n-1}{n-1}=\binom{n+k-1}{k}$. A non-decreasing $f:[k]\to[n]$ is determined by the multiset of its values (list them in increasing order), and every $k$-multiset arises; a strictly increasing $f$ is determined by its image, a $k$-subset of $[n]$.
(4) Add a slack variable $x_{r+1}=n-(x_1+\cdots+x_r)\ge0$: the solutions of the inequality correspond to the nonnegative solutions of $x_1+\cdots+x_{r+1}=n$, and (1) with $r+1$ variables gives $\binom{n+r}{r}$. ∎
Lower bounds $x_i\ge a_i$ are handled by the substitution $y_i=x_i-a_i$. An upper bound on a single variable is handled by the complement ("subtract the solutions with $x_i\ge c+1$"); several upper bounds need inclusion–exclusion (Example 5). The number of monomials of degree $n$ in $r$ variables — the number of distinct terms in the multinomial expansion — is also $\binom{n+r-1}{r-1}$, since a monomial $x_1^{k_1}\cdots x_r^{k_r}$ is a solution of $\sum k_i=n$.
The Pigeonhole Principle
The pigeonhole principle counts nothing exactly; it proves that something exists. Its strength lies entirely in a well-chosen set of "holes".
Let $f:A\to B$ be a map between finite sets, $|A|=N$, $|B|=k\ge1$ (think of $N$ pigeons in $k$ holes).
- If $N\gt k$, then $f$ is not injective: some hole contains at least two pigeons.
- Generalised form. Some hole contains at least $\lceil N/k\rceil$ pigeons. Equivalently, if $N\ge k(m-1)+1$ then some hole contains at least $m$ pigeons. The bound is sharp: if $N=qk+s$ with $0\le s\lt k$, the pigeons can be placed with no hole holding more than $\lceil N/k\rceil$.
- Averaging form. If $a_1,\dots,a_k$ are real numbers with sum $s$, then $a_i\ge s/k$ for some $i$ and $a_j\le s/k$ for some $j$.
- Infinite form. If $A$ is infinite and $B$ finite, some fibre $f^{-1}(b)$ is infinite.
Proof. (3) If $a_i\lt s/k$ for every $i$, adding gives $s\lt s$; similarly for the other inequality. (2) Apply (3) to the fibre sizes $a_b=|f^{-1}(b)|$, whose sum is $N$: some $a_b\ge N/k$, and since $a_b$ is an integer, $a_b\ge\lceil N/k\rceil$. If $N\ge k(m-1)+1$ then $N/k\gt m-1$, so $\lceil N/k\rceil\ge m$. For sharpness put $q+1$ pigeons in each of $s$ holes and $q$ in each of the other $k-s$: the largest hole holds $q+1$ pigeons if $s\gt0$ and $q$ if $s=0$, which is $\lceil N/k\rceil$ in both cases. (1) is (2) with $N\ge k+1$, as then $\lceil N/k\rceil\ge2$. (4) $A$ is the union of the finitely many fibres; a finite union of finite sets is finite. ∎
- Read the conclusion as "two objects share a property"; the property defines the holes. Common holes: remainders on division by $n$; pairs $\{r,n-r\}$ of remainders (for "sum or difference divisible by $n$"); the odd part of an integer (for "one divides the other"); small squares or triangles of a subdivision (for "two points are close"); possible values of a function (degrees, lengths, partial sums).
- Count: you need at least one more pigeon than holes (or $k(m-1)+1$ pigeons to force $m$ in a hole).
- Test sharpness: an extremal example with one pigeon fewer shows that your number is the best possible — exam questions asking for "the least number that guarantees…" need both halves.
Proof. Let the sequence be $a_1,\dots,a_{mn+1}$. To each index $k$ attach the pair $(i_k,d_k)$, where $i_k$ is the length of the longest increasing subsequence ending at $a_k$ and $d_k$ the length of the longest decreasing subsequence ending at $a_k$. We claim that the pairs are distinct. Let $j\lt k$. If $a_j\lt a_k$, appending $a_k$ to a longest increasing subsequence ending at $a_j$ gives an increasing subsequence of length $i_j+1$ ending at $a_k$, so $i_k\gt i_j$. If $a_j\gt a_k$, the same argument gives $d_k\gt d_j$. (The terms are distinct, so one of the two cases occurs.) In either case $(i_j,d_j)\ne(i_k,d_k)$.
Now suppose that $i_k\le m$ and $d_k\le n$ for all $k$. Then the $mn+1$ distinct pairs lie in the set $[m]\times[n]$ of $mn$ pairs — impossible by the pigeonhole principle. So some $i_k\ge m+1$ or some $d_k\ge n+1$. For sharpness, take $m$ blocks of $n$ numbers, each block decreasing and every number of a block larger than every number of the previous block; for $m=n=3$: $3,2,1,\ 6,5,4,\ 9,8,7$. An increasing subsequence uses at most one term from each block (length $\le m$), and a decreasing subsequence stays inside one block (length $\le n$). ∎
Proof. Write $\{t\}=t-\lfloor t\rfloor\in[0,1)$ for the fractional part. The $N+1$ numbers $\{0\cdot\alpha\},\{1\cdot\alpha\},\dots,\{N\alpha\}$ lie in $[0,1)$, which is the union of the $N$ intervals $\left[\tfrac jN,\tfrac{j+1}N\right)$, $j=0,\dots,N-1$. By the pigeonhole principle two of them, $\{a\alpha\}$ and $\{b\alpha\}$ with $0\le a\lt b\le N$, lie in the same interval, so $\left|\{b\alpha\}-\{a\alpha\}\right|\lt\tfrac1N$. Put $q=b-a\in[1,N]$ and $p=\lfloor b\alpha\rfloor-\lfloor a\alpha\rfloor$. Then $q\alpha-p=\{b\alpha\}-\{a\alpha\}$, so $|q\alpha-p|\lt\tfrac1N$, and dividing by $q$ gives $\left|\alpha-\tfrac pq\right|\lt\tfrac1{qN}\le\tfrac1{q^2}$.
Now let $\alpha$ be irrational. We first show that infinitely many pairs $(p,q)$ with $q\ge1$ satisfy $|q\alpha-p|\lt1/q$. Given any finite list $(p_1,q_1),\dots,(p_s,q_s)$ of such pairs, $\delta=\min_j|q_j\alpha-p_j|$ is positive because $\alpha$ is irrational. Choose $N$ with $1/N\lt\delta$; the first part gives a pair $(p,q)$ with $1\le q\le N$ and $|q\alpha-p|\lt1/N\le1/q$. Since $|q\alpha-p|\lt\delta$, this pair is not on the list. So no finite list is complete. Finally, a fixed rational number $x$ (necessarily $x\ne\alpha$) can be written as $p/q$ with $|\alpha-x|\lt1/q^2$ only for $q\lt|\alpha-x|^{-1/2}$, i.e. in finitely many ways; infinitely many pairs therefore give infinitely many distinct fractions $p/q$ with $|\alpha-p/q|\lt1/q^2$. ∎
Inclusion–Exclusion, Derangements and Surjections
The sum rule handles disjoint sets. When the sets overlap we must correct for the overlaps — then correct the corrections, and so on. The bookkeeping is the principle of inclusion–exclusion.
Let $A_1,\dots,A_n$ be subsets of a finite set $X$, and for $S\subseteq[n]$ let $A_S=\bigcap_{i\in S}A_i$, with $A_\varnothing=X$. Then the number of elements of $X$ lying in none of the $A_i$ is $$\Bigl|X\setminus\bigcup_{i=1}^nA_i\Bigr|=\sum_{S\subseteq[n]}(-1)^{|S|}\,|A_S|,$$ and, equivalently, $$\Bigl|\bigcup_{i=1}^nA_i\Bigr|=\sum_{k=1}^{n}(-1)^{k-1}\sum_{|S|=k}|A_S|.$$ Symmetric case. If $|A_S|=N_k$ depends only on $k=|S|$, the first sum is $\sum_{k=0}^n(-1)^k\binom nkN_k$. Bonferroni inequalities. Truncating the first sum after the terms with $|S|\le t$ gives an upper bound for the left side when $t$ is even and a lower bound when $t$ is odd.
Proof. Count the contribution of a single element $x\in X$ to the right-hand side. Let $M=\{i:x\in A_i\}$ and $m=|M|$. Then $x\in A_S$ exactly when $S\subseteq M$, so $x$ contributes $$\sum_{S\subseteq M}(-1)^{|S|}=\sum_{j=0}^{m}(-1)^j\binom mj=(1-1)^m,$$ which is $1$ if $m=0$ and $0$ if $m\ge1$ (Theorem 5.3). Summing over $x$, the right side counts exactly the elements in no $A_i$. The second form follows by subtracting from $|X|=|A_\varnothing|$. In the symmetric case there are $\binom nk$ sets $S$ of size $k$, each contributing $(-1)^kN_k$.
For Bonferroni, the truncated sum receives from $x$ the contribution $c_t(m)=\sum_{j=0}^{t}(-1)^j\binom mj$. For $m=0$ this is $1$. For $m\ge1$, Pascal's rule $\binom mj=\binom{m-1}j+\binom{m-1}{j-1}$ makes the sum telescope: $$c_t(m)=\sum_{j=0}^{t}(-1)^j\binom{m-1}{j}-\sum_{j=0}^{t-1}(-1)^{j}\binom{m-1}{j}=(-1)^t\binom{m-1}{t}.$$ So the truncated sum equals the true count plus $(-1)^t\sum_{x:\,m(x)\ge1}\binom{m(x)-1}{t}$, a correction that is $\ge0$ for even $t$ and $\le0$ for odd $t$. ∎
Proof. Let $X$ be the set of all $k^n$ functions $[n]\to[k]$ and $A_i$ the set of functions whose image misses $i$. A function in $A_S$ takes values in $[k]\setminus S$, so $|A_S|=(k-|S|)^n$ depends only on $|S|$. The surjections are the functions in no $A_i$; apply the symmetric case of Theorem 5.10. A surjection from an $n$-set onto a larger set cannot exist, and a surjection between two $n$-sets is a bijection. ∎
- $\displaystyle D_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$, i.e. $D_n=\sum_{k=0}^n(-1)^k\binom nk(n-k)!$, for all $n\ge0$.
- $D_n=(n-1)\bigl(D_{n-1}+D_{n-2}\bigr)$ for $n\ge2$.
- $D_n=nD_{n-1}+(-1)^n$ for $n\ge1$.
- For $n\ge1$, $\left|D_n-\dfrac{n!}{e}\right|\lt\dfrac1{n+1}\le\dfrac12$, so $D_n$ is the integer nearest to $n!/e$, and $D_n/n!\to1/e$.
- The number of permutations of $[n]$ with exactly $k$ fixed points is $\binom nkD_{n-k}$; hence $\sum_{k=0}^n\binom nkD_{n-k}=n!$.
Proof. (1) Let $X$ be the set of all $n!$ permutations and $A_i=\{\sigma:\sigma(i)=i\}$. A permutation in $A_S$ fixes every element of $S$ and permutes the other $n-|S|$ elements arbitrarily, so $|A_S|=(n-|S|)!$. The symmetric case of inclusion–exclusion gives $D_n=\sum_k(-1)^k\binom nk(n-k)!=\sum_k(-1)^k\frac{n!}{k!}$.
(2) Let $\sigma$ be a derangement of $[n]$, $n\ge2$, and let $i=\sigma(n)$; then $i\ne n$, so there are $n-1$ choices of $i$, and by symmetry each choice gives the same number of derangements. Fix $i$ and split into two cases. Case 1: $\sigma(i)=n$. Then $\sigma$ swaps $i$ and $n$, and its restriction to the remaining $n-2$ elements is an arbitrary derangement of them: $D_{n-2}$ possibilities. Case 2: $\sigma(i)\ne n$. Let $j=\sigma^{-1}(n)$; then $j\ne n$ and $j\ne i$. "Short-circuit" the path $j\to n\to i$: define $\tau$ on $[n-1]$ by $\tau(j)=i$ and $\tau(x)=\sigma(x)$ for $x\ne j$. Then $\tau$ is a permutation of $[n-1]$ with no fixed point ($\tau(j)=i\ne j$). Conversely, from a derangement $\tau$ of $[n-1]$ we recover $\sigma$ by putting $j=\tau^{-1}(i)$, $\sigma(j)=n$, $\sigma(n)=i$ and $\sigma(x)=\tau(x)$ otherwise; this $\sigma$ is a derangement with $\sigma(n)=i$ and $\sigma(i)=\tau(i)\ne n$. So Case 2 contributes $D_{n-1}$, and $D_n=(n-1)(D_{n-1}+D_{n-2})$.
(3) Splitting off the last term of (1), $D_n=n\cdot(n-1)!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}+n!\frac{(-1)^n}{n!}$, and the right side is $nD_{n-1}+(-1)^n$.
(4) Since $e^{-1}=\sum_{k\ge0}(-1)^k/k!$, we get $\frac{n!}{e}-D_n=n!\sum_{k\gt n}\frac{(-1)^k}{k!}$, which equals $$(-1)^{n+1}\left(\frac1{n+1}-\frac1{(n+1)(n+2)}+\cdots\right).$$ This alternating series has strictly decreasing terms, so its absolute value is less than its first term $\frac1{n+1}\le\frac12$. Dividing by $n!$ gives $D_n/n!\to1/e$.
(5) Choose the $k$ fixed points ($\binom nk$ ways) and a derangement of the other $n-k$ elements ($D_{n-k}$ ways). Every permutation has exactly one set of fixed points, so summing over $k$ counts all $n!$ permutations. ∎
| $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| $D_n$ | 1 | 0 | 1 | 2 | 9 | 44 | 265 | 1854 | 14833 | 133496 | 1334961 |
Stirling Numbers, Set Partitions, and Counting Functions and Relations
Surjections from $[n]$ onto $[k]$ distribute $n$ distinct objects into $k$ labelled nonempty boxes. If the boxes are unlabelled, we are counting partitions of $[n]$ into $k$ blocks — and, because equivalence relations correspond to partitions (Unit 1, §1.1), equivalence relations with $k$ classes.
- $S(n,k)=S(n-1,k-1)+k\,S(n-1,k)$ for $n,k\ge1$.
- $\operatorname{surj}(n,k)=k!\,S(n,k)$; hence $\displaystyle S(n,k)=\frac1{k!}\sum_{j=0}^{k}(-1)^j\binom kj(k-j)^n$.
- $S(n,1)=S(n,n)=1$, $\ S(n,2)=2^{n-1}-1$ and $S(n,n-1)=\binom n2$ (for $n\ge1$, resp. $n\ge2$).
- $\displaystyle x^n=\sum_{k=0}^{n}S(n,k)\,x^{\underline k}$ as polynomials in $x$, where $x^{\underline k}=x(x-1)\cdots(x-k+1)$.
- $\displaystyle B_{n+1}=\sum_{k=0}^{n}\binom nkB_k$ for $n\ge0$.
Proof. (1) In a partition of $[n]$ into $k$ blocks, either $\{n\}$ is a block — and removing it leaves a partition of $[n-1]$ into $k-1$ blocks — or $n$ lies in a block with other elements; removing $n$ leaves a partition of $[n-1]$ into $k$ blocks, and $n$ could have been added to any one of those $k$ blocks. Both correspondences are bijective.
(2) A surjection $f:[n]\to[k]$ determines the partition of $[n]$ into its $k$ nonempty fibres $f^{-1}(1),\dots,f^{-1}(k)$, together with the labelling "fibre $\leftrightarrow$ value". Conversely each partition into $k$ blocks and each of the $k!$ bijections from its blocks to $[k]$ give one surjection. So every partition arises from exactly $k!$ surjections (division rule). Combine with Theorem 5.11.
(3) A partition into two blocks is $\{B,[n]\setminus B\}$ with $\varnothing\ne B\ne[n]$; there are $2^n-2$ such $B$, and $B$ and its complement give the same partition, so $S(n,2)=\frac{2^n-2}2$. A partition of $[n]$ into $n-1$ blocks has one block of size $2$ and $n-2$ singletons, and is determined by the $2$-block.
(4) Let $x=m\in\mathbb{N}$. Count the $m^n$ functions $[n]\to[m]$ by the size $k$ of their image: the image can be chosen in $\binom mk$ ways and the function is then a surjection onto it, so the number with image size $k$ is $\binom mk\,k!\,S(n,k)=m^{\underline k}S(n,k)$. Hence $m^n=\sum_kS(n,k)m^{\underline k}$ for every positive integer $m$. Both sides are polynomials in $x$ of degree at most $n$ that agree at infinitely many points, so they are equal.
(5) In a partition of $[n+1]$, let $T$ be the set of elements that share a block with $n+1$, and let $k=n-|T|$. The block of $n+1$ is $\{n+1\}\cup T$, and the remaining blocks form a partition of the $k$-set $[n]\setminus T$. There are $\binom nk$ choices of the set $[n]\setminus T$ and $B_k$ partitions of it. ∎
| $S(n,k)$ | $k=1$ | 2 | 3 | 4 | 5 | 6 | 7 | $B_n$ |
|---|---|---|---|---|---|---|---|---|
| $n=1$ | 1 | 1 | ||||||
| 2 | 1 | 1 | 2 | |||||
| 3 | 1 | 3 | 1 | 5 | ||||
| 4 | 1 | 7 | 6 | 1 | 15 | |||
| 5 | 1 | 15 | 25 | 10 | 1 | 52 | ||
| 6 | 1 | 31 | 90 | 65 | 15 | 1 | 203 | |
| 7 | 1 | 63 | 301 | 350 | 140 | 21 | 1 | 877 |
Proof. In a permutation of $[n]$ with $k$ cycles, either $n$ is a fixed point — remove it to get a permutation of $[n-1]$ with $k-1$ cycles — or $n$ lies in a longer cycle $\cdots\to a\to n\to b\to\cdots$; replacing this by $\cdots\to a\to b\to\cdots$ gives a permutation of $[n-1]$ with $k$ cycles, and $n$ can be re-inserted after any of the $n-1$ elements $a$. This proves the recurrence. Let $P_n(x)=x(x+1)\cdots(x+n-1)$; then $P_n(x)=P_{n-1}(x)\,(x+n-1)$, so the coefficient of $x^k$ in $P_n$ is (coefficient of $x^{k-1}$ in $P_{n-1}$) $+\,(n-1)\cdot$(coefficient of $x^k$ in $P_{n-1}$). The coefficients of $P_n$ therefore satisfy the same recurrence and initial values as $c(n,k)$, and they agree. Putting $x=1$ gives $n!$; the coefficient of $x$ is $1\cdot2\cdots(n-1)$; the coefficient of $x^{n-1}$ is $0+1+\cdots+(n-1)=\binom n2$. ∎
| balls / boxes | any number per box | at most one per box | at least one per box |
|---|---|---|---|
| distinct / distinct | $k^n$ | $k^{\underline n}$ | $k!\,S(n,k)$ |
| identical / distinct | $\binom{n+k-1}{k-1}$ | $\binom kn$ | $\binom{n-1}{k-1}$ |
| distinct / identical | $\sum_{j=0}^{k}S(n,j)$ | $1$ if $n\le k$, else $0$ | $S(n,k)$ |
| identical / identical | partitions of $n$ into at most $k$ parts | $1$ if $n\le k$, else $0$ | partitions of $n$ into exactly $k$ parts |
The last row involves integer partitions, which have no closed formula; for small $n$ list them (e.g. $7$ into exactly $3$ parts: $5{+}1{+}1$, $4{+}2{+}1$, $3{+}3{+}1$, $3{+}2{+}2$ — four ways). Translate every "distribution" question into one cell of this table before computing.
Let $|X|=n\ge1$ and $p=\binom n2=\frac{n(n-1)}2$ (the number of unordered pairs of distinct elements).
There is no simple formula for the number of transitive relations or of partial orders (for $n=1,2,3,4$: $2,13,171,3994$ transitive relations and $1,3,19,219$ partial orders).
Proof. A relation is a choice of $0$ or $1$ for each of the $n^2$ matrix entries. The $n^2$ entries split into the $n$ diagonal entries $M_{ii}$ and $p$ off-diagonal pairs $\{M_{ij},M_{ji}\}$ ($i\lt j$), and each property below is a condition on each diagonal entry and on each pair separately, so the product rule applies. Reflexive: all diagonal entries $1$, the other $n^2-n$ entries free. Symmetric: diagonal free ($2^n$); for each pair, $(M_{ij},M_{ji})\in\{(0,0),(1,1)\}$ ($2^p$). Antisymmetric: diagonal free; each pair $\in\{(0,0),(0,1),(1,0)\}$ ($3^p$). Asymmetric = antisymmetric and irreflexive: $3^p$; reflexive and antisymmetric: $3^p$. Symmetric and antisymmetric: each pair must be $(0,0)$, the diagonal is free. Equivalence relations correspond to partitions (Unit 1, §1.1), and a total order corresponds to the list of the elements in increasing order. A binary operation is a function from the $n^2$ ordered pairs to $X$; a commutative one is determined by its values on the $n+p=\frac{n(n+1)}2$ unordered pairs $\{x,y\}$ (with $x=y$ allowed). The values $2,13,171,3994$ and $1,3,19,219$ were found by checking all $2^{n^2}$ relations by computer. ∎
- "Choose the required ones first" overcounts. Committees of $5$ from $6$ men and $5$ women with at least $2$ women: $\binom52\binom93=840$ is wrong; the answer is $381$ (Example 1). Count the complement or split into disjoint cases.
- Ordered vs unordered. $\binom nk$ counts subsets, $n^{\underline k}$ sequences of distinct elements; $\binom{10}3=120$ but $10^{\underline3}=720$.
- Identical vs distinct. $10$ balls in $4$ boxes: $286$ ways if the balls are identical, $4^{10}$ if they are distinct; stars and bars never applies to distinct objects.
- Circular arrangements. $n$ people round a table: $(n-1)!$, not $n!$; divide by $2$ only if mirror images are identified and $n\ge3$ (for $n=2$ there is one arrangement either way).
- Upper bounds need inclusion–exclusion. $\binom{n+r-1}{r-1}$ ignores upper bounds; with $0\le x_i\le7$, $x_1+x_2+x_3=15$ has $28$ solutions, not $\binom{17}2=136$.
- Stopping inclusion–exclusion early gives only a bound. $k^n-k(k-1)^n$ is a lower bound for the number of surjections, not the number: for $n=6$, $k=4$ it is $1180$, while $\operatorname{surj}(6,4)=1560$.
- Labelled vs unlabelled boxes. Surjections $[n]\to[k]$ number $k!\,S(n,k)$; partitions into $k$ blocks (equivalence relations with $k$ classes) number $S(n,k)$. $\operatorname{surj}(6,4)=1560$ but $S(6,4)=65$.
- Exactly $k$ fixed points. $\binom nkD_{n-k}$, not $\binom nk(n-k)!$ (which counts permutations fixing a chosen set, possibly more). For $n=7$, $k=3$: $315$, not $840$.
- $D_n/n!$ is not monotone. $\tfrac12,\tfrac13,\tfrac38,\tfrac{11}{30},\tfrac{53}{144},\dots$ alternate around $1/e$; $D_n$ is odd exactly when $n$ is even ($D_n\equiv n-1\pmod 2$).
- The pigeonhole bound may not be sharp for the question asked. Five points in a unit square force a pair within $\frac{\sqrt2}2$, but not within $\frac12$ (Example 4(d)); and $n$ pigeons in $n$ holes need not collide at all.
- Erdős–Szekeres needs $mn+1$ terms. $3,2,1,6,5,4,9,8,7$ ($9=3\cdot3$ terms) has no monotone subsequence of length $4$.
- Antisymmetric is not "not symmetric". The empty relation and the identity relation are both symmetric and antisymmetric; on an $n$-set there are $2^n$ relations with both properties. "Asymmetric" is stronger than antisymmetric (it forbids $xRx$).
- Number of terms vs sum of coefficients. $(x_1+\cdots+x_r)^n$ has $\binom{n+r-1}{r-1}$ distinct terms, but its coefficients add up to $r^n$; $(x+y+z)^4$ has $15$ terms and coefficient sum $81$.
Exercises
- 1 How many four-digit numbers (no leading zero) have four distinct digits? How many of these are even?
- 2 In how many ways can $5$ boys and $4$ girls stand in a row so that no two girls stand next to each other?
- 3 Eight people, among them $A$ and $B$, sit round a circular table. In how many seatings do $A$ and $B$ sit next to each other? Directly opposite each other?
- 4 A convex decagon has how many diagonals? If no three diagonals pass through a common interior point, how many intersection points of diagonals lie inside the decagon?
- 5 Find the coefficient of $x^5$ and the constant term in the expansion of $\left(2x-\dfrac1x\right)^9$.
- 6 Prove that $\sum_{k\text{ even}}\binom nk=2^{n-1}$ for $n\ge1$, and that $\displaystyle\sum_{k=0}^{n}\frac{1}{k+1}\binom nk=\frac{2^{n+1}-1}{n+1}$.
- 7 Prove that $\sum_{k=0}^nk^2\binom nk=n(n+1)2^{n-2}$ for $n\ge1$. (Hint: $k^2=k(k-1)+k$.)
- 8 How many subsets of $[10]$ contain no two consecutive integers? (Find a recurrence for the number $a_n$ of such subsets of $[n]$.)
- 9 A lattice path from $(0,0)$ to $(6,4)$ uses unit steps right or up. How many such paths are there? How many pass through $(3,2)$?
- 1 How many distinct arrangements does the word BANANA have? In how many of them are no two A's adjacent?
- 2 How many solutions does $x_1+x_2+x_3+x_4+x_5=12$ have in nonnegative integers? In positive integers?
- 3 How many solutions does $x_1+x_2+x_3\le10$ have in nonnegative integers?
- 4 In how many ways can $15$ identical chocolates be shared among $4$ children so that each child gets at least $2$ and at most $6$?
- 5 Find the coefficient of $x^2y^3z^2$ in $(x-2y+3z)^7$.
- 6 How many distinct terms does $(a+b+c+d)^8$ have after like terms are collected? What is the sum of all its coefficients?
- 7 How many functions $f:[5]\to[7]$ are non-decreasing? Strictly increasing?
- 8 A composition of $n$ is an ordered sum of positive integers equal to $n$ (so $1+2$ and $2+1$ are different compositions of $3$). How many compositions does $10$ have? How many use only parts $1$ and $2$?
- 9 Find the coefficient of $x^{10}$ in $(1+x+x^2+x^3)^4$ in two ways: by inclusion–exclusion and by a symmetry of the polynomial.
- 1 How many cards must be drawn from a standard pack of $52$ (four suits of $13$) to be sure of four cards of the same suit? To be sure of at least one card of every suit?
- 2 Prove that among any $101$ integers chosen from $[200]$ one divides another. Show that $100$ integers do not suffice.
- 3 Prove that in every group of $n\ge2$ people, two have the same number of friends within the group (friendship is mutual).
- 4 Prove that among any $52$ integers there are two whose sum or difference is divisible by $100$. Is $51$ enough?
- 5 Show that every sequence of $17$ distinct real numbers has a monotone subsequence of length $5$, and write down a sequence of $16$ distinct numbers with no monotone subsequence of length $5$.
- 6 Ten points lie in a closed equilateral triangle of side $3$. Prove that two of them are at distance at most $1$.
- 7 Prove that some power $3^k$ with $k\ge1$ ends in the digits $001$.
- 8 Prove that among any $6$ people there are $3$ who all know each other or $3$ who are pairwise strangers, and that $5$ people do not suffice.
- 9 Apply Theorem 5.9 with $\alpha=\sqrt2$ and $N=10$: find integers $1\le q\le10$ and $p$ with $|q\sqrt2-p|\lt\tfrac1{10}$. Is your pair the only one?
- 1 How many integers in $[1,2100]$ are divisible by none of $3$, $5$, $7$?
- 2 How many permutations $\sigma$ of $[8]$ satisfy $\sigma(i)\ne i$ for every even $i$?
- 3 Compute $D_7$ from the recurrence $D_n=(n-1)(D_{n-1}+D_{n-2})$ and compare with $7!/e$.
- 4 Eight letters are put at random into eight addressed envelopes. In how many ways are exactly $3$ letters in the right envelope? At least $6$?
- 5 Find the number of surjections from a $7$-set onto a $3$-set, and deduce $S(7,3)$.
- 6 Compute the row $S(6,k)$, $k=1,\dots,6$, from the row $n=5$ by the recurrence of Theorem 5.13, and check $B_6=203$ using $B_{n+1}=\sum\binom nkB_k$.
- 7 Six different books are packed into $3$ identical boxes. In how many ways if no box may be empty? If boxes may be empty? If the boxes are labelled and none may be empty?
- 8 On a $3$-element set, how many relations are reflexive and antisymmetric? How many are neither reflexive nor irreflexive?
- 9 Prove that $D_n$ is even if and only if $n$ is odd ($n\ge1$).
- 10 An involution is a permutation $\sigma$ with $\sigma\circ\sigma=\mathrm{id}$. Show that the number $t_n$ of involutions of $[n]$ satisfies $t_n=t_{n-1}+(n-1)t_{n-2}$, and compute $t_6$.
E1. CSIR Part B GATE MA The number of surjective functions from a set with $6$ elements onto a set with $4$ elements is (A) $65$; (B) $1180$; (C) $1560$; (D) $4096$.
E2. CSIR Part B The number of permutations of $\{1,2,\dots,7\}$ that have exactly three fixed points is (A) $210$; (B) $315$; (C) $840$; (D) $1854$.
E3. CSIR Part B The number of solutions of $x_1+x_2+x_3=15$ in integers with $0\le x_i\le7$ for each $i$ is (A) $28$; (B) $36$; (C) $64$; (D) $136$.
E4. CSIR Part C Let $D_n$ be the number of derangements of $\{1,\dots,n\}$. Which of the following statements are true? (One or more options may be correct.) (A) For $n\ge1$, $D_n$ is odd if and only if $n$ is even. (B) The sequence $D_n/n!$, $n\ge2$, is decreasing. (C) For every $n\ge1$, the number of permutations of $\{1,\dots,n\}$ with exactly one fixed point differs from $D_n$ by exactly $1$. (D) $D_n/n!\lt1/e$ for every $n\ge2$.
E5. CSIR Part C Which of the following statements are true? (One or more options may be correct.) (A) Among any $13$ integers there are two whose difference is divisible by $12$. (B) Among any $5$ points in a closed equilateral triangle of side $1$ there are two at distance at most $\tfrac12$. (C) Every sequence of $9$ distinct real numbers has a monotone subsequence of length $4$. (D) Among any $5$ integers chosen from $\{1,2,\dots,10\}$ there are two, one of which divides the other.
E6. CSIR Part C Let $X$ be a set with $4$ elements. Which of the following statements are true? (One or more options may be correct.) (A) There are $4096$ reflexive relations on $X$. (B) There are $2^{12}$ symmetric relations on $X$. (C) There are exactly $7$ equivalence relations on $X$ with exactly two equivalence classes. (D) There are exactly $16$ relations on $X$ that are both symmetric and antisymmetric.
Suggested plan — 3 lectures × 60 min (plus an optional problem class on the Exam corner).
- Counting principles. Theorem 5.1 with the handshake lemma as the first double count; Theorems 5.2–5.4, proving every identity by a story (committee with a chair, red and blue balls). Do Example 1(c) live: let the class compute $840$ first, then ask them to find a committee that was counted three times. End with the four-model table of the strategy box.
- Repetition and pigeonholes. Multinomial coefficients (MISSISSIPPI), stars and bars — project Interactive 1 in all three modes; in mode $x_i\le c$ ask the class to predict the number of surviving solutions before the run ends. Example 3. Then the pigeonhole principle, Erdős–Szekeres (draw the pairs $(i_k,d_k)$ for a short sequence on the board) and Example 4; Dirichlet's theorem if time allows.
- Inclusion–exclusion. Prove Theorem 5.10 by "follow one element", surjections, derangements and the recurrences (Theorem 5.12); project Interactive 2 and let it run while you discuss Example 6. Finish with Stirling numbers, the balls-into-boxes table and Theorem 5.15 on relations (Example 7).
Discussion questions. (1) Why does the probability that nobody draws their own name hardly depend on the number of people? What would change if people drew with replacement? (2) The pigeonhole principle proves existence without construction: in Example 4(c), how would you actually find the block, and how long does it take? (3) Symmetry and antisymmetry are conditions on pairs of matrix entries, so the counts factorise; why is there no product formula for transitive relations?
Misconceptions to watch for. Choosing "the required ones first" (overcounting); mixing up identical and distinct objects or boxes; forgetting that circular arrangements are counted up to rotation; using stars and bars without the upper bounds; stopping inclusion–exclusion after the first correction; $S(n,k)$ vs $k!\,S(n,k)$; "exactly $k$ fixed points" computed as $\binom nk(n-k)!$; believing "antisymmetric" means "not symmetric"; claiming a pigeonhole bound without checking sharpness.
Suggested homework. I(1, 3, 5, 8), II(1, 4, 5, 9), III(2, 3, 4, 7), IV(1, 2, 4, 6, 7, 8); Exam corner E1, E3, E4, E6.
Research question. When $n$ objects are matched to $n$ labels completely at random, how close is the number of correct matches to a Poisson distribution with mean $1$ — and how should a "matching test" be judged?
Why it matters. Matching tests are used in psychology and sensory science: a wine taster who claims to recognise grape varieties is given $n$ unlabelled glasses and $n$ labels, and the number of correct matches is compared with what pure guessing would give. Under guessing, the matching is a uniformly random permutation and the number of correct matches is its number of fixed points. The same distribution decides how often an office or school gift exchange has to be redrawn because someone drew their own name — and it goes back to Montmort's analysis of the card game Treize in 1708.
What to do.
- Using Theorem 5.12(5), compute the exact distribution $p_n(k)=\binom nkD_{n-k}/n!$ of the number of fixed points for $n=5$, $8$, $10$, and compare it with the Poisson probabilities $e^{-1}/k!$. Measure the gap by the total variation distance $\tfrac12\sum_k|p_n(k)-e^{-1}/k!|$ (include the Poisson tail beyond $k=n$).
- Simulate $10^5$ random permutations of $[10]$ with the Fisher–Yates shuffle and compare the observed frequencies with $p_{10}(k)$.
- For a tasting test with $n=8$ glasses, find the smallest number $c$ of correct matches such that $P(X\ge c)\lt0.05$ under guessing. Would $3$ correct matches convince you?
- A gift exchange is redrawn until nobody has their own name. Show that the number of draws is geometric with success probability $D_n/n!$, and compute its mean for $n=6$ and as $n\to\infty$.
Tools: Python with exact fractions (fractions.Fraction) and a random-number generator; or a spreadsheet for steps 1 and 3.
Hand in: A one-page note with a table of $p_n(k)$ against $e^{-1}/k!$, your total variation distances, the critical value $c$ for $n=8$, and the mean number of draws.
Going further. Prove that the $j$-th factorial moment of the number of fixed points, $E[X(X-1)\cdots(X-j+1)]$, equals $1$ for every $j\le n$ (double count $j$-tuples of distinct fixed points), and explain why this forces convergence to the Poisson distribution. Read about the problème des ménages (Lucas, 1891), where couples must not sit next to each other, and how inclusion–exclusion solves it.
🧪 Self-check quiz
Q1. In how many ways can $7$ identical balls be placed in $3$ labelled boxes (boxes may be empty)?
Q2. The number of derangements of a $5$-element set is
Q3. What is the least number of people that guarantees that at least three of them were born in the same calendar month?
Q4. The Stirling number $S(5,2)$ — the number of ways to split a $5$-element set into two nonempty unlabelled blocks — is
Q5. How many symmetric relations are there on a set with $3$ elements?