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.

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

Answer 3

Don't know if this one classifies as famous, but it is a nice illustration. If $K$ is a finite field with $q$ elements, then the field with $q^m$ elements is contained (as a unique subfield) in the field of $q^n$ elements if and only if $m$ divides $n$. Therefore the number of elements in the field of $q^n$ elements not contained in any proper subfield is, by inclusion-exclusion, given by $$ \sum_{d\mid n} \mu(d)q^{n/d} $$ and the number of irreducible polynomials in $K[X]$ of degree $n$ is$$ \frac1n{\sum_{d\mid n} \mu(d)q^{n/d}}, $$ by the attribution of its minimal polynomial to each element of an algebraic extension of $K$.

Answer 4

Here is an inclusion-exclusion based on max and min: for any finite set $(T_s)_{s\in {\cal S}}$ of numbers we have $$\bigvee_{s\in {\cal S}} T_s =\sum (-1)^{|A|-1} \bigwedge_{s\in A} T_s\tag1$$ where the sum runs over all non-empty subsets $A$ of $\cal S$.

If $(X_n)$ is a Markov chain with state space ${\cal S}$, and $T_s:=\inf(n\geq 0: X_n=s)$ is the hitting time of state $s$, then the left hand side of (1) is called the cover time. It's the number of steps until every state in ${\cal S}$ is hit.

Calculating the average cover time for a Markov chain is considered a pretty tough problem. In contrast, finding the average of the time $\wedge_{s\in A}\ T_s$ to hit a subset $A$ is fairly standard. That's why I was very surprised to learn the connection between these two problems via (1). I first saw this in Robert Israel's beautiful answer to this MO question.

Answer 5

There are some nice applications of the inclusion-exclusion principle.

1. Problème des ménages and Relaxed ménage problem. There are some solutions here

2. Also from the link above we understand that Problème des ménages is a problem equivalent to a problem in the knot theory.

3. The number of surjective functions. I added some applications in MSE here

4. The number of Latin rectangles here