Skip to main content
3 of 3
http -> https (the question was bumped anyway)
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

No doubts, the inclusion-exclusion principle generates most common type of formulae used in enumerative combinatorics. Examples include explicit formulae for derangements, Striling numbers, rook polynomials, Euler's totient function, and so on.

$$\left\lvert \bigcup_{i=1}^n A_i \right\rvert = \sum_{\emptyset\ne J\subseteq\{1,2,\dots,n\}} (-1)^{|J|-1} \left\lvert \bigcap_{j\in J}^n A_j \right\rvert$$

Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152