Pigeonhole and Inclusion-Exclusion - Core Definitions

The Pigeonhole Principle and the Principle of Inclusion-Exclusion are two fundamental tools in discrete mathematics that provide elegant solutions to counting problems involving constraints and overlapping sets. These principles have applications ranging from number theory to computer science.

DefinitionPigeonhole Principle (Basic Form)

If $n$ objects are placed into $k$ boxes where $n > k$ , then at least one box must contain more than one object.

More formally, if $n$ objects are distributed among $k$ boxes, then at least one box contains at least $\lceil n/k \rceil$ objects, where $\lceil x \rceil$ denotes the ceiling function (smallest integer greater than or equal to $x$ ).

The pigeonhole principle, despite its simplicity, is remarkably powerful. It guarantees the existence of an object with a certain property without constructively finding it. This is an example of a non-constructive existence proof.

ExampleBirthday Problem Variant

In any group of 13 people, at least two people must have birthdays in the same month.

This follows directly from the pigeonhole principle: 13 people (objects) distributed among 12 months (boxes) means at least one month contains at least $\lceil 13/12 \rceil = 2$ people.

DefinitionGeneralized Pigeonhole Principle

If $n$ objects are distributed among $k$ boxes, then either:

At least one box contains at least $\lceil n/k \rceil$ objects, or
At least one box contains at most $\lfloor n/k \rfloor$ objects

where $\lfloor x \rfloor$ denotes the floor function (largest integer less than or equal to $x$ ).

DefinitionPrinciple of Inclusion-Exclusion (Two Sets)

For finite sets $A$ and $B$ , the number of elements in their union is: $|A \cup B| = |A| + |B| - |A \cap B|$

This principle corrects for overcounting: when we add $|A|$ and $|B|$ , elements in both sets are counted twice, so we must subtract $|A \cap B|$ once.

The inclusion-exclusion principle extends to any number of sets, providing a systematic method for counting elements in unions while accounting for all overlaps.

DefinitionPrinciple of Inclusion-Exclusion (General Form)

For finite sets $A_1, A_2, \ldots, A_n$ , the cardinality of their union is: $\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i=1}^{n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n|$

More compactly, this can be written as: $\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{\emptyset \neq S \subseteq \{1,2,\ldots,n\}} (-1)^{|S|+1} \left|\bigcap_{i \in S} A_i\right|$

Remark

The inclusion-exclusion principle alternates between adding and subtracting intersection terms. The intuition is that we must correct for elements counted multiple times: elements in exactly $k$ sets are counted $\binom{k}{1}$ times in the first sum, subtracted $\binom{k}{2}$ times in the second sum, added $\binom{k}{3}$ times in the third sum, and so on. The binomial theorem ensures that the net count is exactly once: $\sum_{i=1}^{k} (-1)^{i+1}\binom{k}{i} = 1$ .

These foundational principles provide powerful techniques for solving existence and counting problems in discrete mathematics.