Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
    
Since !n/n! ~ 1/e, can you solve the modified equation with this substituted? –  marty cohen Jun 15 '12 at 5:40
    
@martycohen I think this substitution is illegal. –  Frank Science Jun 15 '12 at 5:42
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

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

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