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