An alternative way to solve a classic problem of combinatorics

Question

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

Answer 1

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!}. $$

Answer 2

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.