# An alternative way to solve a classic problem of combinatorics

The problem is to count how many permutations in $$S_n$$ have no fixed points. Let call this number $$f(n)$$, and define the set $$N=\{1,\ldots,n\}$$.

The 'classic' solution is using the exclusion-inclusion principle to get

\begin{align*}n!&=f(n)+\sum_{k=1}^n\sum_{A\subseteq N,\#A=k}(-1)^k\#\{\sigma\in S_n: j\in A\to\sigma(j)=j\}\\ &=f(n)+\sum_{k=1}^n(-1)^k\binom nk(n-k)!\\ &=f(n)+n!\sum_{k=1}^n\frac{(-1)^k}{k!}\end{align*}

My alternative try:

I have tried to define recursively the sequence $$f(n)$$ as follows:

Let $$B(A)=\#\{\sigma\in S_n: \sigma(j)=j \leftrightarrow j\in A\}$$ for $$A\subseteq N$$ (note the 'iff' in the definition).

$$f(0)=1$$

\begin{align*} f(n)&=n!-\sum_{k=0}^{n-1}\sum_{A\subseteq N,\#A=k}B(A)\\ &=n!-\sum_{k=0}^{n-1}\binom nkf(n-k)\\ &=n!-\sum_{k=0}^{n-1}\binom nkf(k)\end{align*}

My question:

I'm struggling if there is a way to get the former result from the latter (that is, to solve the reecursive equation) avoiding the exclusion-inclusion principle, i.e,. by purely 'algebraic' means.

My thoughts:

This suggests that I should prove that

$$n!\sum_{k=1}^n\frac{(-1)^k}{k!}=\sum_{k=0}^{n-1}\binom nkf(k)$$

I have tried induction to no avail so far.

Another alternative way

Since a permutation can be expressed uniquely as a product of disjoint cycles, we can solve the problem for $$n=7$$ this way:

A permutation with no fixed points can be expressed as a product of disjoint cycles of order $$\ge 2$$.

• If the order of cycles are 2-2-3, there are $$\frac{\binom 72\binom 52\binom 33(2-1)!(2-1)!(3-1)!}{2!}=210$$ permutations.
• If it is 3-4, there are $$\binom 73\binom 44(3-1)!(4-1)!=420$$.
• If it is 2-5, there are $$\binom 72\binom 55(2-1)!(5-1)!=504$$.
• If it is a 7-cycle, there are $$(7-1)!=720$$.

The sum is $$1854$$.

But I guess that this is difficult to do for arbitrary $$n$$.

Your alternative equation can be written $$n!=\sum_{k=0}^n\binom nkf(k).\tag1$$ From this, we can derive the exponential generating function for $$f$$, and hence derive the original formula $$f(k)$$. Multiplying both sides of $$(1)$$ by $$\frac{x^n}{n!}$$, we get $$x^n=\frac{x^n}{n!}\sum_{k=0}^n \binom nk f(k)=x^n\sum_{k=0}^n \frac{f(k)}{k!}\cdot \frac1{(n-k)!}\tag2$$ Next, summing both sides of $$(2)$$ from $$n=0$$ to $$\infty$$, we get $$\frac1{1-x}=\sum_{n=0}^\infty x^n\sum_{k=0}^n \frac{f(k)}{k!}\cdot \frac1{(n-k)!}\tag3$$ You can now recognize that the RHS of $$(3)$$ is the series which is the Cauchy product of the series $$\sum_{k=0}^\infty \frac{f(k)}{k!}x^k$$ with the series $$\sum_{\ell=0}^\infty \frac{1}{\ell!}x^\ell$$. The latter has closed form $$e^x$$, so we obtain $$\frac1{1-x}=e^x\cdot \sum_{k=0}^\infty \frac{f(k)}{k!}x^k.$$

Therefore, $$\sum_{k=0}^n f(k)\frac{x^k}{k!}=\frac{e^{-x}}{1-x}.\tag4$$ You can then recover the original formula for $$f(n)$$. From $$(4)$$, we have that $$f(n)=n!\cdot [x^n] \Big( e^{-x}\cdot (1-x)^{-1}\Big)$$ Finally, $$[x^n] \Big( e^{-x}\cdot (1-x)^{-1}\Big)$$ is given by the convolution of the sequence of coefficients for $$e^{-x}$$ and the sequence of coefficients for $$\frac1{1-x}$$. $$f(n)=n!\cdot [x^n]\frac{e^{-x}}{1-x}=n![x^n]\left(\sum_i \frac{x^i(-1)^i}{i!}\right)\left(\sum_{j=0}^\infty x^j\right)=n!\sum_{k=0}^n\frac{(-1)^k}{k!}.$$

• You mean $\frac{x^n}{n!}$? I think it would be good to insert one or maybe two additional steps in the algebra there for someone who's never seen this argument before. Commented Jun 28 at 19:33

As Mike says the key is to rewrite the recursion as

$$n! = \sum_{k=0}^n {n \choose k} f(k).$$

In general, suppose you are in a situation where you have two sequences $$a_n$$ and $$b_n$$ related by the identity

$$a_n = \sum_{k=0}^n {n \choose k} b_k.$$

This is sometimes called the binomial transform, although there appear to be three slightly different things called this name, two of which insert signs.

Theorem ("binomial inversion"): The above identity is equivalent to the identity $$b_n = \sum_{k=0}^n (-1)^{n-k} {n \choose k} a_k.$$

This is the "inverse binomial transform" (although again, as a warning, conventions differ on where the signs should be inserted) and the desired identity readily follows.

The theorem can be proven in at least four different ways I can think of, all of which are arguably equivalent. The first is to use inclusion-exclusion. The second is to use Möbius inversion on a poset, namely the poset of subsets of an $$n$$-element set; this is essentially a more general way to phrase what inclusion-exclusion is doing. The third and fourth proofs use generating functions, and interestingly this is a case where either ordinary or exponential generating functions can be used. Both effectively "do the inclusion-exclusion automatically for you."

Mike's proof generalizes as follows. Write $$A(x) = \sum a_n \frac{x^n}{n!}$$ and $$B(x) = \sum b_n \frac{x^n}{n!}$$. Then

\begin{align*} A(x) &= \sum_{n=0}^{\infty} \frac{x^n}{n!} \sum_{k=0}^n {n \choose k} b_k \\ &= \sum_{n=0}^{\infty} \sum_{k=0}^n \frac{x^{n-k}}{(n-k)!} b_k \frac{x^k}{k!} \\ &= \sum_{k=0}^{\infty} b_k \frac{x^k}{k!} \sum_{n=k}^{\infty} \frac{x^{n-k}}{(n-k)!} \\ &= \sum_{k=0}^{\infty} b_k \frac{x^k}{k!} e^x \\ &= e^x B(x). \end{align*}

The key step is the third line where we interchange the order of summation. The algebra here can be avoided if you know how exponential generating functions multiply, I just want to be explicit if you're seeing this for the first time. This gives $$B(x) = e^{-x} A(x)$$, and then you expand this back out again. So the binomial and inverse binomial transform are really simple in terms of exponential generating functions, you just multiply and divide by $$e^x$$ respectively. This is closely analogous to the proof of Möbius inversion using Dirichlet series, where you just multiply and divide by $$\zeta(s)$$ respectively.

The fourth proof uses ordinary rather than exponential generating functions and is a little harder. Now write $$F(x) = \sum a_n x^n, G(x) = \sum b_n x^n$$ (no factorials). Then

\begin{align*} F(x) &= \sum_{n=0}^{\infty} \sum_{k=0}^n {n \choose k} b_k x^n \\ &= \sum_{k=0}^{\infty} b_k x^k \sum_{n=k}^{\infty} {n \choose k} x^{n-k} \\ &= \sum_{k=0}^{\infty} b_k \frac{x^k}{(1 - x)^{k+1}} \\ &= \frac{1}{1 - x} G \left( \frac{x}{1 - x} \right) \end{align*}

where on the second line we interchange the order of summation and on the third line we need a generating function identity for $$\frac{1}{(1 - x)^{k+1}}$$; see stars and bars. This can be inverted to express $$G$$ in terms of $$F$$ by substituting $$y = \frac{x}{1 - x}$$, which gives $$x = \frac{y}{1 + y}$$, so

$$G(y) = \frac{1}{1 + y} F \left( \frac{y}{1 + y} \right).$$

Then this can be expanded back out. In this case the exponential generating functions are clearly nicer but sometimes in other situations the ordinary generating functions are nicer.