Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.