19
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .