Unit 3-Lecture 5: The Pigeonhole Principle and Inclusion-Exclusion

1 The Pigeonhole Principle

Pigeonhole Principle: If there are more pigeons than holes they occupy, then at least two pigeons must be in the same hole. Generalized Pigeonhole Principle: If |a|>k⋅|b| , then every total function f：A→B maps at least k+1 different elements of A to the same element of B.

2 Inclusion-Exclusion

Union of n Sets:

|S1∪S2∪...∪Sn|=∑ϕ≠I⊆1...n(−1)|I|+1|⋂i∈ISi|

---

Reference

[1] Lehman E, Leighton F H, Meyer A R. Mathematics for Computer Science[J]. 2015.