Combinatorics: Pigeonhole Principle, Stars & Bars & Derangements

Basic Principle (Dirichlet): If k + 1 or more items are placed into k bins, at least one bin must contain at least 2 items.

Generalized Principle:

If N objects are placed into k boxes, then at least one box must contain at least lceil N / k rceil objects.

Inverted Problem (Guaranteeing a Quota):

How many items N must be chosen to guarantee that at least m items fall into the same category across k categories?

By worst-case analysis: place m - 1 items into each of the k categories without achieving the quota. The very next item forces the quota:

N_{min} = k * (m - 1) + 1.

Stars and Bars (Combinations with Repetition):

The number of ways to distribute r identical items into n distinct labeled bins (or non-negative integer solutions to x_1 + x_2 + ... + x_n = r with x_i >= 0):

binom{n + r - 1}{r} = frac{(n + r - 1)!}{r! (n - 1)!}.

Derangements (Permutations with No Fixed Points):

A derangement is a permutation of {1, 2, ..., n} where no element appears in its original position (pi(i) != i for all i).

Using the Principle of Inclusion-Exclusion (PIE):

D_n = n! sum_{k=0}^n frac{(-1)^k}{k!} = n! [ 1 - frac{1}{1!} + frac{1}{2!} - frac{1}{3!} + ... + frac{(-1)^n}{n!} ].