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.

  • $\begingroup$ Since !n/n! ~ 1/e, can you solve the modified equation with this substituted? $\endgroup$ Jun 15 '12 at 5:40
  • $\begingroup$ @martycohen I think this substitution is illegal. $\endgroup$
    – Yai0Phah
    Jun 15 '12 at 5:42

Expanding my comment, since comments are lousy for math, if we replace !n/n! by 1/e and let H be the LHS, $H = Hwe^{z-1}+ 1-w$ or $H = \frac{1-w}{1-we^{z-1}}$.

You can then substitute, differentiate, and mutilate to your heart's desire.

As to how well this fits your original problem, I don't know.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.