Unit 3: Combinatorial Analysis, Pigeonhole Principle & Inclusion-Exclusion

1. The Fundamental Rules of Enumeration

Enumerative combinatorics is the rigorous mathematical discipline of counting finite discrete configurations.

1. The Rule of Sum (Addition Principle):

If a task can be done in either one of $n_1$ ways or one of $n_2$ ways, where the two sets of ways are mutually disjoint ($A \cap B = \emptyset$), then the task can be performed in:

More generally, for pairwise disjoint sets $A_1, A_2, \dots, A_k$:

2. The Rule of Product (Multiplication Principle):

If a procedure can be broken down into a sequence of two independent steps, where step 1 can be carried out in $n_1$ ways and subsequent step 2 can be carried out in $n_2$ ways regardless of the choice in step 1, then the total number of ways to execute the sequence is:

2. Permutations (Order Matters)

An $r$-permutation of a set of $n$ distinct elements is an ordered arrangement of $r$ elements selected from the set.

Theorem 3.1 (Permutations without Repetition): The number of $r$-permutations of a set of $n$ distinct elements is:

Proof: By the product rule, the first position can be filled in $n$ ways, the second in $n-1$ ways, down to the $r$-th position in $n - (r - 1) = n - r + 1$ ways. $\blacksquare$

• Permutations with Repetition: If elements can be selected with unlimited replacement, there are $n^r$ distinct ordered sequences of length $r$.
• Permutations with Indistinguishable Elements: The number of permutations of $n$ objects of which $n_1$ are of type 1, $n_2$ are of type 2, $\dots$, $n_k$ are of type $k$ (with $\sum n_i = n$) is given by the multinomial coefficient:

3. Combinations (Order Does Not Matter)

An $r$-combination of a set of $n$ distinct elements is an unordered selection of $r$ elements from the set.

Theorem 3.2 (Combinations without Repetition): The number of $r$-combinations from $n$ distinct elements is:

Proof: Each unordered subset of size $r$ can be ordered in $r!$ distinct ways to form permutations. By the division principle, $\binom{n}{r} \cdot r! = P(n, r) \implies \binom{n}{r} = \frac{n!}{r!(n-r)!}$. $\blacksquare$

1. The Binomial Theorem

Theorem 3.3 (Binomial Theorem): Let $x$ and $y$ be real variables and $n \in \mathbb{N}$. Then:

Combinatorial Proof: The product $(x + y)^n = (x + y)(x + y)\cdots(x + y)$ contains $n$ factors. When expanding, we choose either $x$ or $y$ from each factor. The term $x^{n-k} y^k$ arises whenever we choose $y$ from exactly $k$ factors and $x$ from the remaining $n-k$ factors. The number of ways to pick $k$ factors out of $n$ to supply $y$ is precisely $\binom{n}{k}$. Summing over all $k \in \{0, 1, \dots, n\}$ yields the theorem. $\blacksquare$

2. Fundamental Combinatorial Identities

1. Symmetry Identity:

2. Pascal's Identity:

Combinatorial Proof: Let $S$ have $n$ elements and distinguish element $x_0 \in S$. Subsets of size $k$ either contain $x_0$ (leaving $k-1$ elements to choose from $n-1$) or do not contain $x_0$ (leaving $k$ elements to choose from $n-1$). Summing these disjoint cases proves the identity.

3. Sum of Binomial Coefficients:

4. Vandermonde's Convolution Identity:

Theorem 3.4 (Vandermonde's Identity): For positive integers $m, n, r$:

Proof: Consider a group of $m$ men and $n$ women. Choosing a committee of $r$ people from the total $m + n$ pool can be partitioned by the number of men $k \in \{0, 1, \dots, r\}$ on the committee, with the remaining $r - k$ chosen from women. $\blacksquare$

1. Dirichlet's Pigeonhole Principle

Theorem 3.5 (Pigeonhole Principle): If $k + 1$ or more pigeons are placed into $k$ pigeonholes, then there is at least one pigeonhole containing two or more pigeons.

Proof by Contradiction: Assume that no pigeonhole contains two or more pigeons. Then each of the $k$ pigeonholes contains at most 1 pigeon. The total number of pigeons would be at most $k \cdot 1 = k$. But we were given at least $k + 1$ pigeons, a contradiction ($k + 1 \le k$). $\blacksquare$

2. The Generalized Pigeonhole Principle

Theorem 3.6 (Generalized Pigeonhole Principle): If $N$ objects are placed into $k$ boxes, then there is at least one box containing at least:

where $\lceil x \rceil$ is the ceiling function (least integer $\ge x$).

Proof: Assume every box contains at most $\lceil N / k \rceil - 1$ objects. Then the total number of objects is at most:

contradicting the presence of $N$ objects. $\blacksquare$

3. Erdős-Szekeres Monotonic Subsequence Theorem

Theorem 3.7 (Erdős-Szekeres Theorem): Every sequence of $n^2 + 1$ distinct real numbers contains a strictly increasing subsequence of length $n + 1$ or a strictly decreasing subsequence of length $n + 1$.

Proof using Pigeonhole Principle:

1. Let the sequence be $a_1, a_2, \dots, a_{n^2 + 1}$.
2. For each index $k \in \{1, \dots, n^2 + 1\}$, associate the ordered pair $(i_k, d_k)$:

• $i_k$: length of the longest increasing subsequence beginning with $a_k$.
• $d_k$: length of the longest decreasing subsequence beginning with $a_k$.

1. Assume for contradiction that no increasing or decreasing subsequence of length $n + 1$ exists.
2. Then for all $k$, $1 \le i_k \le n$ and $1 \le d_k \le n$.
3. The number of possible distinct pairs $(i, d)$ is $n \times n = n^2$.
4. There are $n^2 + 1$ indices $k$, which act as pigeons placed into $n^2$ box pairs.
5. By the Pigeonhole Principle, there must exist two distinct indices $j < k$ such that $(i_j, d_j) = (i_k, d_k)$.
6. Since all numbers are distinct, either $a_j < a_k$ or $a_j > a_k$:

• If $a_j < a_k$: We can prepend $a_j$ to the longest increasing subsequence starting at $a_k$, yielding an increasing subsequence starting at $a_j$ of length $i_k + 1$. Thus $i_j \ge i_k + 1 > i_k$, contradicting $i_j = i_k$!
• If $a_j > a_k$: We can prepend $a_j$ to the longest decreasing subsequence starting at $a_k$, yielding $d_j \ge d_k + 1 > d_k$, contradicting $d_j = d_k$!

1. In both cases a contradiction arises. Therefore, at least one subsequence of length $n + 1$ must exist. $\blacksquare$

1. The General Principle of Inclusion-Exclusion (PIE)

For two finite sets: $|A \cup B| = |A| + |B| - |A \cap B|$. For three sets:

Theorem 3.8 (General PIE Theorem): Let $A_1, A_2, \dots, A_n$ be finite sets. Then:

Proof: Let an arbitrary element $x$ belong to exactly $m$ of the sets $A_1, \dots, A_n$ (where $1 \le m \le n$). In the RHS summation:

• It is counted $\binom{m}{1}$ times in the single-set terms.
• It is subtracted $\binom{m}{2}$ times in the pairwise intersections.
• In general, it is counted $(-1)^{k-1} \binom{m}{k}$ times in the $k$-wise intersections.

Total times $x$ is counted on the RHS:

Every element in the union is counted exactly once, and any element outside the union is counted 0 times. $\blacksquare$

2. The Number of Surjective (Onto) Functions

Let $|A| = m$ and $|B| = n$ with $m \ge n$. The number of surjective functions $f: A \twoheadrightarrow B$ is:

where $S_2(m, n)$ is the Stirling number of the second kind (partitions of an $m$-set into $n$ non-empty subsets).

3. Derangements ($D_n$ or $!n$)

A derangement is a permutation of $\{1, 2, \dots, n\}$ such that no element appears in its original position ($\forall i, \pi(i) \ne i$).

Theorem 3.9 (Derangement Formula): The number of derangements of $n$ elements is:

As $n \to \infty$, the probability that a random permutation is a derangement rapidly converges to:

1. Stars and Bars Method (Bose-Einstein Statistics)

The problem of distributing $n$ indistinguishable items into $k$ distinguishable bins is isomorphic to counting non-negative integer solutions to:

Theorem 3.10 (Stars and Bars):

1. The number of non-negative integer solutions ($x_i \ge 0$) to $x_1 + \dots + x_k = n$ is:

1. The number of strictly positive integer solutions ($x_i \ge 1$) to $x_1 + \dots + x_k = n$ (with $n \ge k$) is:

Proof (Geometric Stars and Bars):

• Represent the $n$ indistinguishable items as $n$ stars ($*$).
• Bins are demarcated by $k - 1$ divider bars ($|$).
• Any arrangement of $n$ stars and $k-1$ bars represents a unique solution.
• The total number of symbols is $n + (k - 1) = n + k - 1$.
• The number of distinct arrangements is the number of ways to choose the $k-1$ positions for the bars from the total $n + k - 1$ positions: $\binom{n + k - 1}{k - 1}$. $\blacksquare$

2. Interactive Pigeonhole & PIE Venn Diagram Simulator

The interactive simulation below allows visual exploration of:

• Pigeonhole Allocation: Dynamic distribution of pigeons into boxes with real-time detection of overloaded boxes satisfying $\lceil N/k \rceil$.
• 3-Set Inclusion-Exclusion Venn Diagram: Interactive area computation illustrating how overlapping double and triple intersections are compensated.