Pigeonhole and Inclusion-Exclusion - Key Properties

The pigeonhole principle and inclusion-exclusion principle have numerous sophisticated applications that extend far beyond their basic formulations. Understanding these extensions enables us to tackle complex problems in combinatorics, number theory, and graph theory.

DefinitionStrong Pigeonhole Principle

If $n_1 + n_2 + \cdots + n_k + 1$ objects are distributed among $k$ boxes, then for some $i$ (where $1 \leq i \leq k$ ), the $i$ -th box contains at least $n_i + 1$ objects.

When $n_1 = n_2 = \cdots = n_k = n$ , this reduces to: if $kn + 1$ objects are placed in $k$ boxes, at least one box contains at least $n+1$ objects.

This strengthening of the pigeonhole principle provides more precise control over the distribution of objects and is particularly useful in optimization problems.

ExampleSubset Sum Application

Among any 101 integers, there exist two whose difference is divisible by 100.

Proof: Consider the remainders when each integer is divided by 100. There are only 100 possible remainders (0 through 99). By the pigeonhole principle, among 101 integers, at least two must have the same remainder modulo 100. The difference between these two integers is divisible by 100.

DefinitionRamsey Theory Connection

The pigeonhole principle is the simplest case of Ramsey theory, which studies conditions under which order must appear. For example, in any group of 6 people, either 3 are mutual friends or 3 are mutual strangers. This is denoted $R(3,3) = 6$ in Ramsey notation.

DefinitionInclusion-Exclusion for Surjections

The number of surjective (onto) functions from a set of size $n$ to a set of size $k$ is: $k! \cdot S(n,k)$

where $S(n,k)$ is a Stirling number of the second kind. Using inclusion-exclusion, this can also be computed as: $\sum_{i=0}^{k} (-1)^i \binom{k}{i} (k-i)^n$

This formula counts functions where every element in the codomain has at least one preimage, using inclusion-exclusion to subtract functions that miss elements.

ExampleDerangement Formula via Inclusion-Exclusion

The number of permutations of $n$ objects where no object is in its original position is: $D_n = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}$

This is derived using inclusion-exclusion: let $A_i$ be the set of permutations where object $i$ is in position $i$ . We want $\left|\overline{A_1 \cup A_2 \cup \cdots \cup A_n}\right|$ , which equals $n! - |A_1 \cup \cdots \cup A_n|$ , and we apply inclusion-exclusion to the union.

Remark

The inclusion-exclusion principle extends to probability theory through the formula: $P\left(\bigcup_{i=1}^{n} E_i\right) = \sum_{k=1}^{n} (-1)^{k+1} \sum_{|S|=k} P\left(\bigcap_{i \in S} E_i\right)$

This probabilistic version is known as Bonferroni's inequality when truncated at various terms, providing both upper and lower bounds for the probability of a union of events. The connection between combinatorics and probability through inclusion-exclusion is fundamental to probabilistic method in discrete mathematics.

These advanced applications demonstrate how simple principles can yield powerful results across diverse mathematical domains.