Inclusion--Exclusion, Derangements & Pigeonhole

When two sets overlap, adding their sizes counts the overlap twice, so subtract it once:

For three sets, add the singles, subtract the pairs, add back the triple:

To count elements in none of the sets, subtract the union from the universe $|U|$:

For sets $A_1,\dots,A_n$, alternate sums over single sets, pairs, triples, and so on:

Equivalently, the number of elements in none of the sets is

where the empty intersection is the whole universe $|U|$.

A derangement is a permutation in which no element stays in its original position. Inclusion--exclusion over the “$i$ is fixed” events gives

Two handy recurrences: $\ D_n = (n-1)\bigl(D_{n-1}+D_{n-2}\bigr)$ and $\ D_n = nD_{n-1} + (-1)^n.$

As $n$ grows, $D_n/n! \to 1/e \approx 0.3679$, so a random permutation is a derangement about $37\%$ of the time.

The number of surjections (onto functions) from an $n$--element set onto a $k$--element set is found by excluding the maps that miss at least one target value:

This also counts the ways to distribute $n$ distinct objects into $k$ distinct boxes with no box empty. It relates to Stirling numbers of the second kind by

where $S(n,k)$ counts partitions of the objects into $k$ unlabeled nonempty groups.

If $n$ objects are placed into $k$ boxes and $n > k$, then some box contains at least two objects. More sharply: you cannot have every box with at most one object once the objects outnumber the boxes.

The art is choosing the right “boxes.” Common box constructions: remainders modulo $m$, sign/parity classes, sub-regions of a shape, or pairs that sum to a target.

If $n$ objects go into $k$ boxes, then some box contains at least

objects. (If every box had at most $\lceil n/k\rceil - 1$, the total would be under $n$.) Turned around, to force some box to hold at least $r$ objects you need $n > k(r-1)$, i.e. $n = k(r-1)+1$ objects.

Extremal principle: to find the largest “bad-free” set, group elements into forbidden pairs/blocks; you may take at most one representative per block, and the pigeonhole bound is tight when you take exactly one.

Euler's totient $\varphi(n)$ counts integers in $\{1,\dots,n\}$ coprime to $n$. Let $p_1,\dots,p_r$ be the distinct primes dividing $n$; applying the “none of the divisibility events” form of PIE gives the product formula

For example $\varphi(12) = 12\left(1-\tfrac12\right)\left(1-\tfrac13\right) = 12\cdot\tfrac12\cdot\tfrac23 = 4$ (namely $1,5,7,11$). This is the surjection/derangement machinery in disguise: a signed sum over subsets of “forbidden” primes.

Number theory. Among any $n+1$ integers, two are congruent modulo $n$, so their difference is a multiple of $n$. Among any $n+1$ numbers chosen from $\{1,\dots,2n\}$, two are consecutive-in-a-pair and one divides the other (write each as $2^a\cdot(\text{odd})$; there are only $n$ odd parts --- the boxes).

Geometry. Partition a region into smaller cells; if you place more points than cells, two points share a cell and lie within its diameter. E.g. $5$ points in a unit square: cut it into four $\tfrac12\times\tfrac12$ squares, so two points lie within distance $\tfrac{\sqrt2}{2}$.

Many existence problems yield to: consider the largest, smallest, or otherwise most extreme object and argue about it. Choose the configuration maximizing (or minimizing) some quantity; if the desired property failed, you could push the extreme further --- a contradiction. Paired with pigeonhole, the extremal principle proves that a structure must exist without constructing it explicitly.

The Stirling number of the second kind $S(n,k)$ counts the ways to partition an $n$--element set into exactly $k$ nonempty, unlabeled blocks. Building an element one at a time gives the recurrence

(the new element either joins one of the $k$ existing blocks, or starts a fresh block with the previous $n-1$ elements split into $k-1$ blocks). Boundary values: $S(n,0)=[n=0]$, $S(n,1)=S(n,n)=1$, $S(n,2)=2^{n-1}-1$.

Labeling the blocks turns each partition into a surjection, recovering the count from the previous section:

Summing over all block-counts gives the Bell number $B_n=\sum_{k=0}^{n} S(n,k)$, the total number of partitions of an $n$--set.

The Maclaurin series $e^{-1}=\sum_{k\ge 0}\tfrac{(-1)^k}{k!}$ truncated at $k=n$ is exactly $D_n/n!$. The leftover tail is tiny, so

Bounding the alternating tail gives $\left|\,D_n - \tfrac{n!}{e}\,\right| = \tfrac{n!}{e}\left|\sum_{k>n}\tfrac{(-1)^k}{k!}\right| < \dfrac{1}{n+1} \le \tfrac12$ for $n\ge 1$, which is why rounding is always correct. Consequently the probability that a random permutation of $n$ objects is a derangement,

converges extraordinarily fast --- already at $n=6$ we have $D_6/6! = 265/720 = 0.368055\ldots$, agreeing with $1/e$ to three decimals.

Let $S_j = \sum_{|T|=j}\bigl|\bigcap_{i\in T}A_i\bigr|$ be the $j$-th symmetric sum of intersection sizes ($S_0=|U|$). The number of elements lying in exactly $m$ of the sets $A_1,\dots,A_n$ is

and the number in at least $m$ of the sets is

Setting $m=0$ in $E_m$ gives the “none” formula; $m=1$ in $L_m$ gives the ordinary union. Bonferroni inequalities: truncating the alternating series after an odd number of terms over-estimates $|A_1\cup\cdots\cup A_n|$ and after an even number under-estimates it, so partial sums bracket the true count.

Color the edges of a complete graph on $n$ vertices with two colors (say, acquainted / stranger). A monochromatic triangle is three mutually-acquainted or three mutual strangers. The Ramsey number $R(3,3)$ is the least $n$ forcing one to exist.

$R(3,3)\le 6$: Fix a vertex $v$ among $6$. Its $5$ edges get $2$ colors, so by pigeonhole ($\lceil 5/2\rceil = 3$) at least $3$ share a color --- say $v$ is acquainted with $a,b,c$. If any edge among $a,b,c$ is “acquainted,” that edge with $v$ forms an acquainted triangle; otherwise $a,b,c$ are mutual strangers --- a stranger triangle. Either way a monochromatic triangle appears.

$R(3,3)>5$: color the $5$-cycle's edges red and its “diagonals” blue; neither color contains a triangle. Hence $\boxed{R(3,3)=6}$: any party of $6$ has $3$ mutual acquaintances or $3$ mutual strangers.