# An equation about generating functions and subfactorial

As I promised, I clone the problem from Math.SE to here, in order to find a solution.

Suppose $$G_n(w)$$ is a formal power series (really a probability generating function, see the following explanation) of variable $$w$$, try to solve out $$G_n(w)$$ for all $$n\ge0$$ from the formal-power-series equation of variable $$z$$: $$\sum_{n\ge0}z^nG_n(w)=we^z\sum_{n\ge0}\frac{!n}{n!}z^nG_n(w)+1-w\tag1$$ where $$!n$$ is $$n$$-subfactorial which satisfies $$\frac{!n}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!}$$ Any help? Thanks!

The problem is introduced from a google code jam problem named after Gorosort. $$p_{n,m}$$ denotes the probability that sort the $$n$$-derangement with no more than $$m$$ steps, and $$X_n$$ is the random variable for the steps. We have $$p_{n,m}=\Pr(X_n\le m)=\sum_{k=0}^n\frac{\dbinom nk\,(!(n-k))}{n!}p_{n-k,m-1}+[m=n=0]$$ where $$p_{n,m}=0$$ for $$n<0$$ or $$m<0$$, and $$[P]$$ is Iverson bracket. Let $$G_n(w)=E\left(w^{X_n}\right)=\sum_{m\ge0}(p_{n,m}-p_{n,m-1})w^m$$ is the probability generating function where $$[w^m]G_n(w)$$ is the probability sorting with exact $$m$$ steps. So $$G_n(1)=1$$, and we get equation (1).

I want to solve equation (1) generally, really beyond $$G_n\!\!'(1)$$, which is the expected number, not difficult to solve out:

First we have $$\sum_{n\ge0}\frac{!n}{n!}z^n=\sum_{n\ge0}\sum_{0\le k\le n}\frac{(-1)^k}{k!}z^n=\sum_{k\ge0}\frac{(-1)^k}{k!}z^k\sum_{n\ge0}z^n=\frac{e^{-z}}{1-z}\tag2$$ Differentiating both sides of equation (1) and let $$w=1$$, we have $$\sum_{n\ge0}z^nG_n\!\!'(1)=e^z\sum_{n\ge0}\frac{!n}{n!}z^nG_n(1)+e^z\sum_{n\ge0}\frac{!n}{n!}z^nG_n\!\!'(1)-1$$ Notice that $$G_n(1)=1$$, we have $$\sum_{n\ge0}z^nG_n\!\!'(1)=e^z\sum_{n\ge0}\frac{!n}{n!}z^nG_n\!\!'(1)+\frac z{1-z}\tag3$$ We claim that $$G_n\!\!'(1)=n$$ satisfies equation (3), and it's not hard to show the uniqueness of $$G_n\!\!'(1)$$ of equation (3), thus we solve out the $$G_n\!\!'(1)$$. Differentiating both sides of equation (2), we have $$\sum_{n\ge0}\frac{!n}{n!}nz^{n-1}=\frac{ze^{-z}}{(1-z)^2}$$ and the right side of equation (3) becomes $$\frac{z^2}{(1-z)^2}+\frac z{1-z}=\frac z{(1-z)^2}=\sum_{n\ge0}nz^n$$ Okay. Finally, $$\mathrm{Mean}(G_n)=G_n\!\!'(1)=n$$, and this is the expected number.