Supongamos $G_n(w)$ es un poder formal de la serie (en realidad una probabilidad de generación de función, consulte la siguiente explicación) de la variable $w$, intentar resolver $G_n(w)$ todos los $n\ge0$ a partir de la formal-poder-de la serie de la ecuación de la variable $z$: $$\sum_{n\ge0}z^nG_n(w)=we^z\sum_{n\ge0}\frac{!n}{n!}z^nG_n(w)+1-w\tag1$$ donde $!n$ $n$-subfactorial que satisifies $$\frac{!n}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!}$$ Alguna ayuda? Gracias!
El problema se presentó desde google code jam problema nombrado después de Gorosort. $p_{n,m}$ denota la probabilidad de que ordenar la $n$-alteración con no más de $m$, e $X_n$ es la variable aleatoria de los pasos. Tenemos $$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]$$ donde $p_{n,m}=0$ $n<0$ o $m<0$, e $[P]$ es Iverson soporte. Deje $G_n(w)=E\left(w^{X_n}\right)=\sum_{m\ge0}(p_{n,m}-p_{n,m-1})w^m$ es la probabilidad de generación de función, donde la $[w^m]G_n(w)$ es la probabilidad de la clasificación con el exacto $m$ pasos. Por lo $G_n(1)=1$, y obtenemos la ecuación (1).
Quiero resolver la ecuación (1) en general, realmente más allá de $G_n\!\!'(1)$, que es el número esperado, no es difícil de resolver:
En primer lugar tenemos $$\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$$ La diferenciación de ambos lados de la ecuación (1) y deje $w=1$, tenemos $$\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$$ Observe que $G_n(1)=1$, tenemos $$\sum_{n\ge0}z^nG_n\!\!'(1)=e^z\sum_{n\ge0}\frac{!n}{n!}z^nG_n\!\!'(1)+\frac z{1-z}\tag3$$ Pretendemos que $G_n\!\!'(1)=n$ satisface la ecuación (3), y no es difícil mostrar la singularidad de $G_n\!\!'(1)$ de la ecuación (3), por lo que, a resolver el $G_n\!\!'(1)$. La diferenciación de ambos lados de la ecuación (2), tenemos $$\sum_{n\ge0}\frac{!n}{n!}nz^{n-1}=\frac{ze^{-z}}{(1-z)^2}$$ y por el lado derecho de la ecuación (3) se convierte en $$\frac{z^2}{(1-z)^2}+\frac z{1-z}=\frac z{(1-z)^2}=\sum_{n\ge0}nz^n$$ Bien. Finalmente, $\mathrm{Mean}(G_n)=G_n\!\!'(1)=n$, y este es el número esperado.
