Chapter 5 · Combinatorics and Number Theory

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.

📐 Theorem 5.1 — The basic counting principles

Let $A$, $B$ be finite sets.

  1. Sum rule. If $A\cap B=\varnothing$ then $|A\cup B|=|A|+|B|$; in general $|A\cup B|=|A|+|B|-|A\cap B|$.
  2. 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$.
  3. Bijection rule. If there is a bijection $A\to B$ then $|A|=|B|$.
  4. Division rule. If $f:A\to B$ is surjective and every fibre $f^{-1}(b)$ has exactly $d$ elements, then $|A|=d\,|B|$.
  5. 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.

📘 Definition 5.1 — Factorials, permutations and combinations

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$.
📐 Theorem 5.2 — Counting permutations, combinations and functions

Let $0\le k\le n$.

  1. 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.
  2. $\displaystyle\binom nk=\frac{n^{\underline k}}{k!}=\frac{n!}{k!\,(n-k)!}$.
  3. 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. ∎

📐 Theorem 5.3 — The binomial theorem
Let $x$, $y$ be elements of a commutative ring (numbers, polynomials, or commuting matrices) and $n\ge0$ an integer. Then $$(x+y)^n=\sum_{k=0}^{n}\binom nk x^ky^{n-k}.$$ In particular $\sum_{k=0}^n\binom nk=2^n$ and, for $n\ge1$, $\sum_{k=0}^n(-1)^k\binom nk=0$.

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

📐 Theorem 5.4 — Binomial identities

For integers $n,m,k\ge0$ (with $\binom ab=0$ when $b\lt0$ or $b\gt a$):

Symmetry$\binom nk=\binom n{n-k}$ for $0\le k\le n$.
Pascal's rule$\binom nk=\binom{n-1}{k-1}+\binom{n-1}k$ for $n\ge1$.
Absorption$k\binom nk=n\binom{n-1}{k-1}$ for $n\ge1$.
Vandermonde$\sum_{j}\binom mj\binom n{k-j}=\binom{m+n}k$.
Hockey stick$\sum_{i=k}^{n}\binom ik=\binom{n+1}{k+1}$.

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]$. ∎

🧭 Problem-solving strategy — choose the model before you count

Selecting $k$ objects from $n$ kinds: ask two questions — does order matter? may a kind be repeated?

no repetitionrepetition 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.

✏️ Example 1 — Arrangements and selections with restrictions
(a) How many distinct words can be formed from all the letters of MISSISSIPPI? In how many of them are no two S's adjacent? (b) In how many ways can $8$ people sit round a circular table if two of them, $A$ and $B$, refuse to sit next to each other? (c) A committee of $5$ is chosen from $6$ men and $5$ women. How many committees contain at least two women? Explain why the count "choose $2$ women, then any $3$ of the remaining $9$ people" is wrong.
(a) All words The $11$ letters are M ($1$), I ($4$), S ($4$), P ($2$). A word is determined by choosing the $4$ positions of I, then $4$ of the remaining $7$ for S, then $2$ of the remaining $3$ for P: $$\binom{11}{4}\binom74\binom32=330\cdot35\cdot3=34650=\frac{11!}{1!\,4!\,4!\,2!}.$$ (This is the multinomial coefficient of Theorem 5.5.)
(a) S's apart First arrange the $7$ letters M, I, I, I, I, P, P: $\frac{7!}{4!\,2!}=105$ ways. They create $8$ gaps (before, between and after them); the S's must go into $4$ different gaps, chosen in $\binom84=70$ ways. Total $105\cdot70=7350$.
(b) Complement All seatings: $(8-1)!=5040$. Seatings with $A$, $B$ adjacent: glue them into one block, which can be ordered $AB$ or $BA$; we then seat $7$ units round the table in $(7-1)!=720$ ways, so $2\cdot720=1440$. Answer $5040-1440=3600$. Check another way: seat $A$ anywhere (rotations make all seats alike); $B$ has $5$ admissible seats out of $7$, and the other $6$ people fill the rest in $6!$ ways: $5\cdot720=3600$.
(c) Complement All committees: $\binom{11}5=462$. With no woman: $\binom65=6$; with exactly one woman: $5\binom64=75$. So $462-6-75=381$ committees have at least two women.
(c) The trap "$\binom52\binom93=840$" counts a committee with $j\ge3$ women $\binom j2$ times — once for each choice of which two of its women were "the chosen two". For instance $\{W_1,W_2,W_3,M_1,M_2\}$ is produced from $\{W_1,W_2\}$, $\{W_1,W_3\}$ and $\{W_2,W_3\}$. Indeed $840=\binom52\binom63+3\binom53\binom62+6\binom54\binom61+10\binom55=200+450+180+10$, while the correct count is $200+150+30+1=381$. Different choice sequences produced the same object — rule (2) of Theorem 5.1 was violated.
✏️ Example 2 — Proving identities by double counting
Prove, for every $n\ge1$: (a) $\displaystyle\sum_{k=0}^{n}k\binom nk=n2^{n-1}$; (b) $\displaystyle\sum_{k=0}^n\binom nk^2=\binom{2n}{n}$; (c) $\displaystyle\sum_{k=m}^{n}\binom nk\binom km=\binom nm2^{n-m}$ for $0\le m\le n$.
(a) Count pairs $(S,c)$ with $c\in S\subseteq[n]$ (a committee of any size with a chair). Choosing $S$ of size $k$ and then its chair gives $\sum_k k\binom nk$. Choosing the chair $c$ first ($n$ ways) and then any subset of the other $n-1$ people to join ($2^{n-1}$ ways) gives $n2^{n-1}$. (Analytic check: differentiate $(1+x)^n=\sum\binom nkx^k$ and put $x=1$.)
(b) By symmetry $\binom nk^2=\binom nk\binom n{n-k}$, and Vandermonde with $m=n$, $k=n$ gives $\sum_k\binom nk\binom n{n-k}=\binom{2n}n$. In words: an $n$-subset of $n$ red and $n$ blue balls with $k$ red balls is chosen in $\binom nk\binom n{n-k}$ ways.
(c) Count pairs $(K,M)$ with $M\subseteq K\subseteq[n]$, $|M|=m$ (a committee $K$ with a sub-committee $M$ of size $m$). Choosing $K$ first (size $k$) and then $M$ gives the left side. Choosing $M$ first ($\binom nm$ ways) and then deciding for each of the other $n-m$ people whether they join $K$ ($2^{n-m}$ ways) gives the right side.
Check $n=4$: (a) $0+4+12+12+4=32=4\cdot2^3$; (b) $1+16+36+16+1=70=\binom84$; (c) with $m=2$: $6\cdot1+4\cdot3+1\cdot6=24=\binom42\cdot2^2$.

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.

📘 Definition 5.2 — Multisets and multinomial coefficients

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

📐 Theorem 5.5 — Arrangements of a multiset; the multinomial theorem
  1. 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}$.
  2. 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. ∎

📐 Theorem 5.6 — Stars and bars

Let $n\ge0$ and $r\ge1$ be integers.

  1. The equation $x_1+x_2+\cdots+x_r=n$ has exactly $\displaystyle\binom{n+r-1}{r-1}$ solutions in nonnegative integers.
  2. For $n\ge1$ it has exactly $\displaystyle\binom{n-1}{r-1}$ solutions in positive integers.
  3. 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$.
  4. 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$.

Interactive 1 — Stars and Bars, One Solution at a Time

Each solution of $x_1+\cdots+x_r=n$ is shown twice: as $n$ identical balls in $r$ labelled boxes (below) and as a row of $n$ stars and $r-1$ bars (top). Press Play to run through all solutions in order; the counter confirms the formula. In the mode each $x_i\ge1$ the bars may only go into the gaps between stars; in the mode each $x_i\le c$ the over-full solutions are struck out, and the survivors are exactly what inclusion–exclusion counts.

733
solution—
(x₁, …, x_r)—
bar positions—
formula—
valid so far—
✏️ Example 3 — Integer solutions, multisets and multinomial coefficients
(a) How many solutions does $x_1+x_2+x_3+x_4=20$ have in integers with $x_1\ge2$, $x_2\ge1$, $x_3\ge0$ and $0\le x_4\le6$? (b) An ice-cream shop has $4$ flavours. How many different orders of $6$ scoops are there, if an order is determined by how many scoops of each flavour it contains? (c) How many distinct terms does the expansion of $(x+y+z+w)^{10}$ have? Find the coefficient of $x^3y^2z^4$ in $(x+2y-z)^9$. (d) In how many ways can $10$ balls be put into $4$ labelled boxes if the balls are identical? If they are distinct? If they are distinct and the boxes must receive $4$, $3$, $2$, $1$ balls respectively?
(a) Lower bounds Put $y_1=x_1-2$, $y_2=x_2-1$: we need $y_1+y_2+x_3+x_4=17$ with $y_1,y_2,x_3\ge0$ and $0\le x_4\le6$. Without the upper bound there are $\binom{17+3}{3}=\binom{20}3=1140$ solutions (Theorem 5.6(1)).
(a) Upper bound Subtract the solutions with $x_4\ge7$: putting $x_4'=x_4-7$ gives $y_1+y_2+x_3+x_4'=10$, with $\binom{13}3=286$ solutions. Answer $1140-286=854$.
(b) Multisets An order is a $6$-multiset on $4$ flavours: $\binom{4+6-1}{6}=\binom96=84$.
(c) Terms and a coefficient A term is a monomial $x^ay^bz^cw^d$ with $a+b+c+d=10$: $\binom{13}3=286$ terms. By the multinomial theorem with the "letters" $x$, $2y$, $-z$, the coefficient of $x^3y^2z^4$ in $(x+2y-z)^9$ is $$\binom{9}{3,2,4}\cdot2^2\cdot(-1)^4=\frac{9!}{3!\,2!\,4!}\cdot4=1260\cdot4=5040.$$
(d) Three models Identical balls: a solution of $x_1+\cdots+x_4=10$, so $\binom{13}{3}=286$. Distinct balls: each ball chooses its box, $4^{10}=1\,048\,576$. Distinct balls with prescribed box sizes: $\binom{10}{4,3,2,1}=\frac{10!}{4!\,3!\,2!\,1!}=12600$. The three answers differ by orders of magnitude — always decide first whether the objects are distinguishable.

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

📐 Theorem 5.7 — The pigeonhole principle

Let $f:A\to B$ be a map between finite sets, $|A|=N$, $|B|=k\ge1$ (think of $N$ pigeons in $k$ holes).

  1. If $N\gt k$, then $f$ is not injective: some hole contains at least two pigeons.
  2. 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$.
  3. 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$.
  4. 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. ∎

🧭 Problem-solving strategy — finding the pigeons and the holes
  1. 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).
  2. Count: you need at least one more pigeon than holes (or $k(m-1)+1$ pigeons to force $m$ in a hole).
  3. 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.
📐 Theorem 5.8 — Erdős–Szekeres theorem
Let $m,n\ge1$. Every sequence of $mn+1$ distinct real numbers has an increasing subsequence of length $m+1$ or a decreasing subsequence of length $n+1$. The number $mn+1$ cannot be replaced by $mn$.

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$). ∎

📐 Theorem 5.9 — Dirichlet's approximation theorem
For every real $\alpha$ and every $N\in\mathbb{N}$ there are integers $p,q$ with $1\le q\le N$ and $|q\alpha-p|\lt\dfrac1N$. Consequently, if $\alpha$ is irrational, there are infinitely many rationals $p/q$ ($q\ge1$) with $$\left|\alpha-\frac pq\right|\lt\frac1{q^2}.$$

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$. ∎

✏️ Example 4 — Pigeonhole: prove or disprove
Prove or disprove: (a) among any $7$ integers there are two whose sum or difference is divisible by $10$, and $7$ cannot be replaced by $6$; (b) any $51$ numbers chosen from $[100]$ contain two consecutive numbers, and also two numbers one of which divides the other; (c) for any integers $a_1,\dots,a_n$ there are $0\le i\lt j\le n$ with $n\mid a_{i+1}+\cdots+a_j$; (d) among any $5$ points in a closed unit square there are two at distance less than $\tfrac12$.
(a) True Use the $6$ holes $\{0\},\{5\},\{1,9\},\{2,8\},\{3,7\},\{4,6\}$ of remainders mod $10$. Seven integers put two, $x$ and $y$, into the same hole. If $x\equiv y\pmod{10}$ then $10\mid x-y$; otherwise their remainders are $r$ and $10-r$ and $10\mid x+y$. Six integers do not suffice: for $0,1,2,3,4,5$ all pairwise sums lie in $[1,9]$ and all differences in $[1,5]$.
(b) True Consecutive: the $50$ holes $\{1,2\},\{3,4\},\dots,\{99,100\}$ receive $51$ numbers, so one hole receives both its numbers. Divisibility: write each chosen number as $2^e\cdot u$ with $u$ odd. There are $50$ possible odd parts $u\in\{1,3,\dots,99\}$, so two chosen numbers $2^eu$ and $2^fu$ share their odd part, and the smaller divides the larger. Both bounds are sharp: the $50$ odd numbers contain no consecutive pair, and $\{51,52,\dots,100\}$ contains no pair with one dividing the other (the quotient would be at least $2$, but $2\cdot51\gt100$).
(c) True Consider the $n+1$ partial sums $s_0=0,\ s_1=a_1,\ s_2=a_1+a_2,\dots,s_n$. There are only $n$ possible remainders mod $n$, so $s_i\equiv s_j\pmod n$ for some $i\lt j$, and $s_j-s_i=a_{i+1}+\cdots+a_j$ is divisible by $n$. The pigeons are the partial sums, not the $a_i$ themselves.
(d) False The four corners and the centre of the square are five points whose least distance is $\tfrac{\sqrt2}2\approx0.707\gt\tfrac12$. What is true: dividing the square into four closed squares of side $\tfrac12$, two of the five points lie in one small square, at distance at most its diagonal $\tfrac{\sqrt2}{2}$; the configuration above shows that $\tfrac{\sqrt2}2$ is the best possible constant.

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.

📐 Theorem 5.10 — 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$. ∎

📐 Theorem 5.11 — Counting surjections
For integers $n,k\ge0$, the number of surjections from an $n$-set onto a $k$-set is $$\operatorname{surj}(n,k)=\sum_{j=0}^{k}(-1)^j\binom kj(k-j)^n.$$ In particular $\operatorname{surj}(n,k)=0$ for $k\gt n$ and $\operatorname{surj}(n,n)=n!$, which gives the identities $\sum_{j=0}^{k}(-1)^j\binom kj(k-j)^n=0$ for $n\lt k$ and $=n!$ for $n=k$.

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

✏️ Example 5 — Inclusion–exclusion at work
(a) How many integers in $[1,1000]$ are divisible by none of $2,3,5$? (b) Four ordinary dice are thrown. In how many of the $6^4$ outcomes is the sum $15$? (c) How many arrangements of the letters A, A, B, B, C, C have no two equal letters adjacent?
(a) Let $A_p$ be the multiples of $p$ in $[1,1000]$; $|A_S|=\lfloor1000/\prod_{p\in S}p\rfloor$ because a number is divisible by distinct primes iff it is divisible by their product. So the count is $$1000-(500+333+200)+(166+100+66)-33=266.$$ (For $N=900$, divisible by $30$, the count would be exactly $900\cdot\tfrac12\cdot\tfrac23\cdot\tfrac45=240$ — the product formula for $\varphi$ in §5.3 is this computation.)
(b) Translate With $y_i=x_i-1$ we need $y_1+y_2+y_3+y_4=11$ with $0\le y_i\le5$. Let $A_i=\{y_i\ge6\}$. In $A_S$ substitute $y_i'=y_i-6$ for $i\in S$: the sum becomes $11-6|S|$, so $|A_S|=\binom{11-6|S|+3}{3}$ when $11-6|S|\ge0$ and $0$ otherwise.
(b) Count $$\binom{14}3-\binom41\binom83+\binom42\cdot0=364-224=140.$$ Only $|S|\le1$ contributes, because two variables cannot both be $\ge6$ when the total is $11$. Check by symmetry: the number of outcomes with sum $15$ equals the number with sum $28-15=13$ ($x_i\mapsto7-x_i$), and both are $140$.
(c) All arrangements: $\frac{6!}{2!2!2!}=90$. Let $A_1$ be the arrangements with the two A's adjacent, and $A_2$, $A_3$ the same for B, C. Gluing AA into one block: $|A_1|=\frac{5!}{2!2!}=30$; gluing two pairs: $|A_1\cap A_2|=\frac{4!}{2!}=12$; gluing all three: $3!=6$. By symmetry, $$90-3\cdot30+3\cdot12-6=30.$$
📘 Definition 5.3 — Fixed points and derangements
A fixed point of a permutation $\sigma$ of $[n]$ is an $i$ with $\sigma(i)=i$. A derangement is a permutation with no fixed point. $D_n$ denotes the number of derangements of $[n]$, with $D_0=1$ (the empty permutation has no fixed point) and $D_1=0$.
📐 Theorem 5.12 — Derangements
  1. $\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$.
  2. $D_n=(n-1)\bigl(D_{n-1}+D_{n-2}\bigr)$ for $n\ge2$.
  3. $D_n=nD_{n-1}+(-1)^n$ for $n\ge1$.
  4. 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$.
  5. 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$012345678910
$D_n$10129442651854148331334961334961
Interactive 2 — The Hat-Check Problem and Inclusion–Exclusion

Left: $n$ people (top) collect $n$ hats (bottom) at random; a red arrow is a fixed point (someone got their own hat). Press Play to make many random draws and watch the proportion of draws with no fixed point settle near $D_n/n!\approx1/e$. Right: the inclusion–exclusion partial sums $\sum_{k\le t}(-1)^k/k!$ for $t=0,1,\dots,n$; they overshoot and undershoot $D_n/n!$ in turn (the Bonferroni inequalities) and hit it exactly at $t=n$.

6
this draw: fixed points—
D_n and D_n / n!—
draws · derangements—
observed proportion—
1/e0.367879
✏️ Example 6 — A gift exchange
Six friends put their names in a hat and each draws one name at random (all $6!$ outcomes equally likely). (a) In how many outcomes does nobody draw their own name, and what is the probability? (b) In how many outcomes do exactly two people draw their own names? At least one person? (c) Show that, averaged over all $n!$ permutations of $[n]$, the number of fixed points is exactly $1$, for every $n\ge1$.
(a) Using the recurrence $D_n=nD_{n-1}+(-1)^n$ from $D_1=0$: $D_2=1$, $D_3=2$, $D_4=9$, $D_5=44$, $D_6=6\cdot44+1=265$. The probability is $\frac{265}{720}=\frac{53}{144}\approx0.3681$, within $0.0002$ of $1/e\approx0.3679$.
(b) Exactly two: $\binom62D_4=15\cdot9=135$ (Theorem 5.12(5)) — not $\binom62\cdot4!=360$, which would allow further fixed points. At least one: $720-265=455$.
(c) Double counting Count the pairs $(\sigma,i)$ with $\sigma(i)=i$. For each of the $n$ choices of $i$ there are $(n-1)!$ permutations fixing $i$, so there are $n\cdot(n-1)!=n!$ pairs. Hence the total number of fixed points over all permutations is $n!$, and the average is $1$.
Check For $n=6$ the distribution of the number $k$ of fixed points is $\binom6kD_{6-k}$: $265,264,135,40,15,0,1$ for $k=0,\dots,6$. These add up to $720$, and $\sum k\cdot(\text{count})=264+270+120+60+0+6=720$, so the average is $1$.

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.

📘 Definition 5.4 — Stirling numbers of the second kind and Bell numbers
A partition of a set $X$ into $k$ blocks is an unordered collection of $k$ nonempty, pairwise disjoint subsets of $X$ whose union is $X$. The Stirling number of the second kind $S(n,k)$ is the number of partitions of $[n]$ into $k$ blocks; $S(0,0)=1$, $S(n,0)=0$ for $n\ge1$, and $S(n,k)=0$ for $k\gt n$. The Bell number $B_n=\sum_{k=0}^nS(n,k)$ is the number of all partitions of $[n]$, i.e. the number of equivalence relations on an $n$-set.
📐 Theorem 5.13 — Properties of $S(n,k)$ and $B_n$
  1. $S(n,k)=S(n-1,k-1)+k\,S(n-1,k)$ for $n,k\ge1$.
  2. $\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$.
  3. $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$).
  4. $\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)$.
  5. $\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$234567$B_n$
$n=1$11
2112
31315
4176115
51152510152
61319065151203
7163301350140211877
📘 Definition 5.5 — Stirling numbers of the first kind
Every permutation of $[n]$ splits $[n]$ into disjoint cycles $i\to\sigma(i)\to\sigma^2(i)\to\cdots\to i$ (fixed points are cycles of length $1$; cycle notation is developed in §6.3). The (unsigned) Stirling number of the first kind $c(n,k)$ is the number of permutations of $[n]$ with exactly $k$ cycles; $c(0,0)=1$.
📐 Theorem 5.14 — Properties of $c(n,k)$
For $n,k\ge1$, $$c(n,k)=c(n-1,k-1)+(n-1)\,c(n-1,k),$$ and for $n\ge1$ $$\sum_{k}c(n,k)\,x^k=x(x+1)\cdots(x+n-1);$$ consequently $\sum_kc(n,k)=n!$, $\ c(n,1)=(n-1)!$, $\ c(n,n)=1$ and $c(n,n-1)=\binom n2$.

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$. ∎

🧭 Problem-solving strategy — $n$ balls into $k$ boxes
balls / boxesany number per boxat most one per boxat 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 / identicalpartitions 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.

📘 Definition 5.6 — Properties of a relation
A relation $R$ on a set $X$ is a subset of $X\times X$; write $xRy$ for $(x,y)\in R$. $R$ is reflexive if $xRx$ for all $x$; irreflexive if $xRx$ for no $x$; symmetric if $xRy\Rightarrow yRx$; antisymmetric if $xRy$ and $yRx$ imply $x=y$; asymmetric if $xRy\Rightarrow$ not $yRx$; transitive if $xRy$ and $yRz$ imply $xRz$. On $X=[n]$, $R$ is recorded by its $n\times n$ $0$–$1$ matrix $M$ with $M_{ij}=1\iff iRj$.
📐 Theorem 5.15 — Counting relations and operations on an $n$-set

Let $|X|=n\ge1$ and $p=\binom n2=\frac{n(n-1)}2$ (the number of unordered pairs of distinct elements).

All relations$2^{n^2}$
Reflexive (or irreflexive)$2^{n^2-n}=2^{n(n-1)}$
Symmetric$2^{n}\cdot2^{p}=2^{n(n+1)/2}$
Reflexive and symmetric$2^{p}=2^{n(n-1)/2}$
Antisymmetric$2^n\cdot3^{p}$
Asymmetric; reflexive and antisymmetric$3^{p}$ each
Symmetric and antisymmetric$2^n$ (subsets of the diagonal)
Equivalence relations; total orders$B_n$; $\ n!$
Binary operations $X\times X\to X$$n^{n^2}$, of which $n^{n(n+1)/2}$ are commutative

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

✏️ Example 7 — Functions and relations: compute, prove or disprove
(a) How many functions $f:[5]\to[5]$ satisfy $f\circ f=f$? (b) On a $4$-element set, how many relations are symmetric? antisymmetric? How many equivalence relations have exactly two classes? (c) Prove or disprove: for $1\le k\le n$, the number of equivalence relations on $[n]$ with exactly $k$ classes equals the number of surjections $[n]\to[k]$. (d) How many functions $[6]\to[4]$ have an image with exactly $2$ elements?
(a) Structure Let $I=f([n])$ be the image. If $y=f(x)\in I$ then $f(y)=f(f(x))=f(x)=y$: $f$ fixes every point of its image. Conversely, any $f$ that fixes a set $I$ pointwise and maps the other points into $I$ satisfies $f\circ f=f$. So $f$ is determined by $I$ (with $|I|=k\ge1$) and by the images of the $n-k$ points outside $I$, each chosen in $I$: $$\#\{f:f\circ f=f\}=\sum_{k=1}^{n}\binom nk k^{n-k}.$$
(a) Count For $n=5$: $5\cdot1+10\cdot2^3+10\cdot3^2+5\cdot4+1=5+80+90+20+1=196$ (confirmed by checking all $5^5=3125$ functions by computer).
(b) With $n=4$, $p=6$: symmetric $2^{4}\cdot2^{6}=2^{10}=1024$; antisymmetric $2^4\cdot3^6=16\cdot729=11664$; equivalence relations with two classes: $S(4,2)=2^3-1=7$ (the partitions $3+1$: four of them, and $2+2$: three).
(c) False Equivalence relations with $k$ classes correspond to partitions into $k$ blocks: $S(n,k)$ of them, whereas $\operatorname{surj}(n,k)=k!\,S(n,k)$, because a surjection also labels the blocks. They agree only for $k=1$. Counterexample: $n=3$, $k=2$: $S(3,2)=3$, but there are $2^3-2=6$ surjections $[3]\to[2]$.
(d) Choose the image ($\binom42=6$ ways), then a surjection of $[6]$ onto it ($2^6-2=62$ ways): $6\cdot62=372$. In general the number of $f:[n]\to[m]$ with image of size exactly $k$ is $\binom mk\,k!\,S(n,k)$ — the term of Theorem 5.13(4).
⚠️ Counterexamples and pitfalls
  1. "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.
  2. Ordered vs unordered. $\binom nk$ counts subsets, $n^{\underline k}$ sequences of distinct elements; $\binom{10}3=120$ but $10^{\underline3}=720$.
  3. 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.
  4. 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).
  5. 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$.
  6. 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$.
  7. 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$.
  8. 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$.
  9. $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$).
  10. 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.
  11. 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$.
  12. 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$).
  13. 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

I
Permutations, combinations and the binomial theorem.
  • 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 First digit $9$ ways (not $0$), then $9$, $8$, $7$: $4536$. Even: if the last digit is $0$, the others in $9\cdot8\cdot7=504$ ways; if it is $2,4,6$ or $8$ ($4$ ways), the first digit has $8$ choices (not $0$, not the last digit) and the middle two $8\cdot7$: $4\cdot8\cdot8\cdot7=1792$. Total $504+1792=2296$. (Choosing the first digit first would make the number of choices for the last digit depend on earlier choices — so start with the most restricted position.)
2 Arrange the boys ($5!$), choose $4$ of the $6$ gaps for the girls ($\binom64$) and arrange the girls in them ($4!$): $120\cdot15\cdot24=43200$.
3 Adjacent: glue $A,B$ ($2$ orders) and seat $7$ units round the table: $2\cdot6!=1440$. Opposite: seat $A$ anywhere (all seats are alike up to rotation); $B$'s seat is then forced and the other $6$ people sit in $6!=720$ ways.
4 Diagonals: $\binom{10}2-10=35$ (segments joining two vertices, minus the sides). Every interior intersection point is the crossing of the two diagonals of a unique convex quadrilateral formed by $4$ of the vertices, and every $4$ vertices give one crossing: $\binom{10}4=210$.
5 The general term is $\binom9k(2x)^{9-k}\left(-\tfrac1x\right)^k=(-1)^k2^{9-k}\binom9kx^{9-2k}$. For $x^5$: $k=2$, coefficient $2^7\binom92=128\cdot36=4608$. A constant term needs $9-2k=0$, impossible for an integer $k$: the constant term is $0$.
6 Adding the expansions of $(1+1)^n$ and $(1-1)^n$ gives $2\sum_{k\text{ even}}\binom nk=2^n+0$. For the second identity integrate $(1+x)^n=\sum\binom nkx^k$ from $0$ to $1$: $\frac{2^{n+1}-1}{n+1}=\sum\binom nk\frac1{k+1}$. (Combinatorially: $\frac{1}{k+1}\binom nk=\frac1{n+1}\binom{n+1}{k+1}$ by absorption, and $\sum_k\binom{n+1}{k+1}=2^{n+1}-1$.)
7 By absorption twice, $k(k-1)\binom nk=n(n-1)\binom{n-2}{k-2}$, so $\sum k(k-1)\binom nk=n(n-1)2^{n-2}$ (for $n\ge2$; both sides are $0$ for $n=1$). Adding $\sum k\binom nk=n2^{n-1}$ (Example 2) gives $n(n-1)2^{n-2}+2n2^{n-2}=n(n+1)2^{n-2}$, which also holds for $n=1$ ($1=1\cdot2\cdot2^{-1}$).
8 A good subset of $[n]$ either omits $n$ (a good subset of $[n-1]$) or contains $n$ and then omits $n-1$ (a good subset of $[n-2]$ plus $n$). So $a_n=a_{n-1}+a_{n-2}$ with $a_0=1$, $a_1=2$: $2,3,5,8,13,21,34,55,89,144$. Answer $a_{10}=144$, the Fibonacci number $F_{12}$. (Equivalently $a_n=\sum_k\binom{n-k+1}{k}$.)
9 A path is a word with $6$ R's and $4$ U's: $\binom{10}4=210$. Through $(3,2)$: $\binom52$ paths to $(3,2)$ and $\binom52$ from $(3,2)$ to $(6,4)$, so $10\cdot10=100$.
II
Repetition, multinomial coefficients and stars and bars.
  • 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 $\frac{6!}{3!\,2!\,1!}=60$. A's apart: arrange B, N, N ($3$ ways) and put the three A's into $3$ of the $4$ gaps ($\binom43=4$): $12$.
2 $\binom{12+4}{4}=\binom{16}4=1820$; positive: $\binom{11}4=330$.
3 Slack variable (Theorem 5.6(4)): $\binom{10+3}{3}=286$.
4 Put $y_i=x_i-2\in[0,4]$ with $\sum y_i=7$. Without upper bounds $\binom{10}3=120$; the solutions with some $y_i\ge5$ number $4\binom{5}{3}=40$ (two variables cannot both be $\ge5$). Answer $80$.
5 $\binom{7}{2,3,2}(-2)^3\,3^2=210\cdot(-8)\cdot9=-15120$.
6 Monomials of degree $8$ in $4$ variables: $\binom{11}3=165$. Sum of coefficients: put $a=b=c=d=1$: $4^8=65536$.
7 Non-decreasing: $5$-multisets on $[7]$, $\binom{11}5=462$. Strictly increasing: $5$-subsets, $\binom75=21$.
8 Compositions of $n$ into $r$ parts: $\binom{n-1}{r-1}$, so in all $\sum_r\binom9{r-1}=2^9=512$ (choose which of the $9$ gaps between $10$ stars get bars). With parts $1,2$ only: $c_n=c_{n-1}+c_{n-2}$ (according to the last part), $c_1=1$, $c_2=2$, so $c_{10}=89$.
9 The coefficient counts solutions of $x_1+\cdots+x_4=10$ with $0\le x_i\le3$: $\binom{13}3-4\binom93+6\binom53=286-336+60=10$. Symmetry: $x^{12}p(1/x)=p(x)$ for $p=(1+x+x^2+x^3)^4$ (each factor is palindromic), so the coefficient of $x^{10}$ equals that of $x^{2}$, which is the number of solutions of $\sum x_i=2$: $\binom53=10$.
III
The pigeonhole principle.
  • 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 Four of a suit: $4\cdot3+1=13$ cards (with $12$ one can hold three of each suit). Every suit: $3\cdot13+1=40$ (with $39$ cards one could hold three complete suits).
2 Write each number as $2^eu$ with $u$ odd; there are $100$ odd parts in $[200]$, so two of the $101$ numbers share their odd part and the smaller divides the larger. The $100$ numbers $101,\dots,200$ contain no such pair: a proper multiple of $m\ge101$ is at least $202$.
3 The possible numbers of friends are $0,1,\dots,n-1$ ($n$ values), but $0$ and $n-1$ cannot both occur (someone who knows everybody is a friend of the person who knows nobody). So the $n$ people take at most $n-1$ values, and two of them share a value.
4 Holes: $\{0\},\{50\}$ and the $49$ pairs $\{r,100-r\}$ ($1\le r\le49$) of remainders mod $100$: $51$ holes, so $52$ integers put two in one hole; equal remainders give a difference divisible by $100$, remainders $r$ and $100-r$ a sum divisible by $100$. $51$ is not enough: $0,1,\dots,50$ have all sums in $[1,99]$ and all differences in $[1,50]$.
5 $17=4\cdot4+1$: Erdős–Szekeres with $m=n=4$ gives an increasing or decreasing subsequence of length $5$. Sixteen terms: $4,3,2,1,\ 8,7,6,5,\ 12,11,10,9,\ 16,15,14,13$ — increasing subsequences take at most one term per block, decreasing ones stay in one block.
6 Lines parallel to the sides through the points dividing each side into three equal parts cut the triangle into $9$ closed equilateral triangles of side $1$. Two of the $10$ points lie in one of them, and two points of a closed triangle are at distance at most its longest side, $1$.
7 Among the $1001$ numbers $3^0,3^1,\dots,3^{1000}$ two are congruent mod $1000$, say $3^i\equiv3^j$ with $i\lt j$. Then $1000\mid3^i(3^{j-i}-1)$, and since $\gcd(3^i,1000)=1$ (cancellation, §5.2), $1000\mid3^{j-i}-1$: $3^{j-i}$ ends in $001$. (In fact $3^{100}\equiv1\pmod{1000}$, and $100$ is the least such exponent; Euler's theorem in §5.3 guarantees at least $3^{400}\equiv1$, since $\varphi(1000)=400$.)
8 Fix a person $P$. Of the other $5$, by the generalised pigeonhole principle at least $\lceil5/2\rceil=3$ are all friends of $P$ or all strangers to $P$; say $Q,R,S$ are friends of $P$. If two of $Q,R,S$ know each other, they form a friendly triple with $P$; if not, $Q,R,S$ are pairwise strangers. (The other case is symmetric.) For $5$ people: seat them round a pentagon and let each know exactly their two neighbours; any $3$ of the $5$ include two neighbours and two non-neighbours.
9 Checking $q=1,\dots,10$: $|q\sqrt2-p|$ is least for $q=5$, $p=7$: $|5\sqrt2-7|\approx0.0711\lt0.1$. It is the only pair: the next best are $q=7$ ($|7\sqrt2-10|\approx0.1005$) and $q=10$ ($\approx0.1421$). Note $\left|\sqrt2-\tfrac75\right|\approx0.0142\lt\tfrac1{25}$.
IV
Inclusion–exclusion, derangements, Stirling numbers, functions and relations.
  • 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$.
Check: a counting calculator (exact integers)
73
C(n, k)—
multisets C(n+k−1, k)—
functions [k]→[n]: nᵏ · injective—
surjections [n]→[k] · S(n, k)—
D_n · B_n—
1 $2100$ is divisible by $3\cdot5\cdot7=105$, so every term is exact: $2100-(700+420+300)+(140+100+60)-20=960=2100\cdot\tfrac23\cdot\tfrac45\cdot\tfrac67$.
2 Let $A_i=\{\sigma(i)=i\}$ for $i\in\{2,4,6,8\}$; $|A_S|=(8-|S|)!$. So $\sum_{j=0}^4(-1)^j\binom4j(8-j)!=40320-20160+4320-480+24=24024$.
3 $D_5=44$, $D_6=5(44+9)=265$, $D_7=6(265+44)=1854$; $7!/e\approx1854.11$, and $1854$ is the nearest integer, as Theorem 5.12(4) predicts.
4 Exactly $3$: $\binom83D_5=56\cdot44=2464$. At least $6$: exactly $6$ gives $\binom86D_2=28$, exactly $7$ is impossible ($D_1=0$: if seven are right, so is the eighth), exactly $8$ gives $1$; total $29$.
5 $3^7-3\cdot2^7+3\cdot1^7=2187-384+3=1806$, and $S(7,3)=1806/3!=301$.
6 Row $5$: $1,15,25,10,1$. Then $S(6,2)=1+2\cdot15=31$, $S(6,3)=15+3\cdot25=90$, $S(6,4)=25+4\cdot10=65$, $S(6,5)=10+5\cdot1=15$, $S(6,1)=S(6,6)=1$; the sum is $203$. And $B_6=\binom50B_0+\binom51B_1+\binom52B_2+\binom53B_3+\binom54B_4+\binom55B_5=1+5+20+50+75+52=203$.
7 Identical boxes, none empty: partitions into $3$ blocks, $S(6,3)=90$. Boxes may be empty: $S(6,1)+S(6,2)+S(6,3)=1+31+90=122$. Labelled boxes, none empty: $3!\cdot90=540=\operatorname{surj}(6,3)$.
8 Reflexive and antisymmetric: diagonal forced, each of the $3$ off-diagonal pairs in $3$ patterns: $3^3=27$. Neither reflexive nor irreflexive: all $2^9=512$, minus $2^6$ reflexive, minus $2^6$ irreflexive (no relation on a nonempty set is both): $512-128=384$.
9 By $D_n=nD_{n-1}+(-1)^n$: if $n$ is even, $nD_{n-1}$ is even and $D_n$ is odd. If $n$ is odd, $n-1$ is even, so $D_{n-1}$ is odd (by the previous case, or $D_0=1$ for $n=1$) and $D_n=nD_{n-1}-1$ is odd·odd $-1$, i.e. even. (Induction on $n$, starting from $D_0=1$.)
10 In an involution of $[n]$, either $n$ is fixed — the rest is an involution of $[n-1]$ — or $n$ is swapped with one of the other $n-1$ elements $j$, and the rest is an involution of the remaining $n-2$ elements. So $t_n=t_{n-1}+(n-1)t_{n-2}$, $t_0=t_1=1$: $t_2=2$, $t_3=4$, $t_4=10$, $t_5=26$, $t_6=26+5\cdot10=76$ (confirmed by listing all $720$ permutations by computer).
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

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

Idea Inclusion–exclusion over the values that are missed (Theorem 5.11).
Compute $4^6-\binom413^6+\binom422^6-\binom431^6=4096-2916+384-4=1560$.
Distractors (A) is $S(6,4)$, which forgets the $4!$ labellings of the blocks; (B) $=4^6-4\cdot3^6$ stops inclusion–exclusion after one correction; (D) counts all functions.
Answer (C).

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

Idea Choose the fixed points, then derange the rest (Theorem 5.12(5)).
Compute $\binom73D_4=35\cdot9=315$. (C) $=35\cdot4!$ also counts permutations with more fixed points; (A) $=35\cdot3!$ is meaningless here; (D) is $D_7$.
Answer (B).

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

Idea Stars and bars, then remove the solutions in which some $x_i\ge8$.
Compute All nonnegative solutions: $\binom{17}2=136$. With $x_1\ge8$: $x_1'+x_2+x_3=7$, $\binom92=36$ solutions; the same for $x_2$, $x_3$. Two variables cannot both be $\ge8$ ($16\gt15$). So $136-3\cdot36=28$.
Check Put $z_i=7-x_i\in[0,7]$: $z_1+z_2+z_3=6$, whose solutions automatically satisfy $z_i\le7$: $\binom82=28$.
Answer (A).

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

(A) True $D_n=nD_{n-1}+(-1)^n$ gives $D_n\equiv n-1\pmod2$ by induction (Exercise IV.9): $D_1,D_2,D_3,\dots=0,1,2,9,44,265,\dots$
(B) False $D_3/3!=\tfrac13\lt\tfrac38=D_4/4!$. The ratios oscillate around $1/e$.
(C) True Exactly one fixed point: $\binom n1D_{n-1}=nD_{n-1}=D_n-(-1)^n$, which differs from $D_n$ by $1$.
(D) False $D_2/2!=\tfrac12\gt1/e$; by Theorem 5.12(4) the sign of $D_n/n!-1/e$ is that of $(-1)^n$.
Answer (A) and (C).

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.

(A) True $13$ integers, $12$ possible remainders mod $12$: two share a remainder.
(B) True Joining the midpoints of the sides cuts the triangle into $4$ closed equilateral triangles of side $\tfrac12$; two of the $5$ points lie in one of them, at distance at most $\tfrac12$.
(C) False $3,2,1,6,5,4,9,8,7$: Erdős–Szekeres needs $3\cdot3+1=10$ terms to force length $4$, and this example shows $9$ do not suffice.
(D) False $\{6,7,8,9,10\}$ has no such pair. (With $6$ integers it is true: only $5$ odd parts $1,3,5,7,9$ occur in $[10]$.)
Answer (A) and (B).

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.

(A) True The $4$ diagonal entries are forced, the other $12$ free: $2^{12}=4096$.
(B) False The $4$ diagonal entries and the $6$ off-diagonal pairs are free: $2^{4+6}=2^{10}=1024$.
(C) True $S(4,2)=2^3-1=7$: four partitions of type $3+1$ and three of type $2+2$.
(D) True Symmetric and antisymmetric forces every off-diagonal entry to be $0$; any subset of the diagonal is allowed: $2^4=16$.
Answer (A), (C) and (D).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min (plus an optional problem class on the Exam corner).

  1. 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.
  2. 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.
  3. 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–Teaching NexusResearch-tutored · optional, about 60 minutes

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.

  1. 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$).
  2. Simulate $10^5$ random permutations of $[10]$ with the Fisher–Yates shuffle and compare the observed frequencies with $p_{10}(k)$.
  3. 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?
  4. 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.

Instructor note: $D_{10}/10!=0.36787946\ldots$ differs from $1/e=0.36787944\ldots$ by about $2.3\times10^{-8}$; the total variation distance is about $0.034$ for $n=5$ and $2.2\times10^{-5}$ for $n=10$. For $n=8$: $P(X\ge3)\approx0.080$ and $P(X\ge4)\approx0.019$, so $c=4$ — three correct matches are not significant at the $5\%$ level. The mean number of draws is $n!/D_n$: $720/265\approx2.717$ for $n=6$, tending to $e\approx2.718$.

🧪 Self-check quiz

0/5 correct

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?