Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Note that Stanley dedicates chapter 2 of Enumerative Combinatoris 1 to Sieve Methods, starting with inclusion-exclusion. Indeed counting derangements is the first example, but other ones are given there as well. –  Marc van Leeuwen Dec 8 '11 at 10:46
add comment

4 Answers

up vote 9 down vote accepted

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


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.
share|improve this answer
    
Bender and Goldman link is 404. –  alancalvitti Jul 27 '13 at 14:47
    
@alancalvitti: Thanks. I'll fix it. –  Mike Spivey Jul 27 '13 at 20:19
add comment

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.

share|improve this answer
add comment

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 algbraic extension of $K$.

share|improve this answer
    
Note that from this one can quickly deduce the "prime number theorem for function fields," namely that the number of irreducible polynomials of norm less than or equal to $N$ is approximately $\frac{N}{\log_q(N)}$ (where the norm of a polynomial of degree $n$ is $q^n$). –  Qiaochu Yuan Dec 8 '11 at 20:39
add comment

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.

share|improve this answer
    
Here's a link to Robert Israel's answer: mathoverflow.net/questions/59244/…. –  Srivatsan Dec 8 '11 at 21:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.