[Math] Famous uses of the inclusion-exclusion principle

Question

The standard textbook example of using the inclusion-exclusion principle is for solving the problem of derangement counting; using inclusion-exclusion (and some basic analysis) it can be shown that $D(n)=\left[\frac{n!}{e}\right]$ which I consider to be quite a beautiful example since it tackles a problem that does not seem to be solvable with such a closed formula in the first place (and also, who expects inclusion-exclusion to yield a closed formula?)

Another standard textbook use is giving a (non-closed) formula for Stirling numbers. This result is less amazing, but is still important enough.

My question is whether there are other nice such examples for using inclusion-exclusion for dealing with "natural" and "famous" problems, preferably problems arising in other fields in mathematics.

Edit: I just remembered another nice example: Proving the formula for $\varphi(n)$ (Euler's totient function) directly (there are other methods as well).

Answer 1

Inclusion-exclusion is a special case of the generalized Möbius inversion formula on a locally finite poset (partially-ordered set). For example:

• If the poset is the subsets of some given set $S$ with set inclusion as the partial order, you get the classic inclusion-exclusion formula.
• If the poset is the positive integers with divisibility as the partial order, you get the usual Möbius inversion formula in number theory (cf. André Nicolas's answer).
• If the poset is the positive integers with "$\leq$" as the partial order, you get the (backwards) finite difference operator.
• If the poset is bonds of a graph with refinement as the partial order, you get the chromatic polynomial of the graph.

So any application of these could be considered a use of the inclusion-exclusion formula, generally speaking.

For more information and examples, see

• The Wikipedia page on incidence algebra.
• Bender and Goldman's "On the Applications of Mobius Inversion in Combinatorial Analysis" (American Mathematical Monthly 82(8) 1975: 789-803).
• Rota's classic "On the Foundations of Combinatorial Theory I: Theory of Möbius Functions" (Probability Theory and Related Fields 2 (4) 1964: 340–368).
• Chapter 3 of Stanley's Enumerative Combinatorics, Vol. 1.

---

I'm not sure I would call them famous, but here are some examples I've seen on MSE. (The second was an answer to one of my questions; all the others are answers I've given.)

• Proving $a!\, b! = \sum_{i=0}^{b}\binom{b}{i}(-1)^{i}\frac{(a+b+1)!}{(a+i+1)}$. See here.
• A combinatorial proof that $\int {x^n e^x dx} = e^x \sum_{k = 0}^n ( - 1)^k \frac{n!}{(n-k)!}x^{n-k} + C$.
• A generalization of the derangement problem involving the number of fixed points with $n$ different permutations (rather than just 1).
• Proving $\sum\limits_{r=0}^n \frac{(-1)^r}{r+1}\binom{n}{r} = \frac1{n+1}$. See here.