MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.