Famous uses of the inclusion-exclusion principle?

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).

Solution 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.

Solution 2:

The following example arose today in a question on MSE. Let $Q(x)$ be the number of square-free integers $\le x$. Then $$\lim_{x\to\infty}\frac{Q(x)}{x}=\prod_{p \text{ prime}}\left(1-\frac{1}{p^2}\right).$$ The product on the right incorporates the principle of Inclusion-Exclusion. If we imagine expanding the product, the term $$-\sum_p \frac{1}{p^2}$$ subtracts the proportions divisible by the various squares of primes. But this counts twice numbers such as $36$ which are divisible by the squares of two distinct primes. So the term $$\sum_{p\ne q} \frac{1}{p^2q^2}$$ adds back the proportions divisible by the squares of two distinct primes, and so on. But that overcounts the proportions divisible by the squares of three distinct primes, and so on. There are quite a few similar uses of Inclusion-Exclusion in Number Theory. Quite often, when the Möbius function $\mu(n)$ is used, Inclusion-Exclusion lies behind the scene.