# generating function for $\sum_{n=0}^{\infty} \{\sum_{i=0}^n {n \choose i}i^i (i-1)^{n-i}\}$

Hi I am looking for a generating function for the sequence: $$\{\sum_{i=0}^n {n \choose i}i^i (i-1)^{n-i}\}_{n=0}^{\infty}$$

Because I am looking for a closed form solution for the series:

$$F(x) = \sum_{n=0}^{\infty} \{\sum_{i=0}^n {n \choose i}i^i (i-1)^{n-i}\}x^n$$

or

$$F(x) = \sum_{n=0}^{\infty} \{\sum_{i=0}^n {n \choose i}i^i (i-1)^{n-i}\}\frac{x^n}{n!}$$

If I could find an exponential generating function $$G(x) = \{n^n\}_{n=0}^{\infty} = \sum_{n=0}^{\infty}n^n\frac{x^n}{n!}$$ then I could solve for $F(x)$:

$$F(x) = G(x)*(xD)G(x) = \sum_{n=0}^{\infty} \{\sum_{i=0}^n {n \choose i}i^i (i-1)^{n-i}\}x^n$$

Edit. The larger problem is that I am trying to prove the following equality: $$n!\sum_{i=0}^{n}\frac{(-1)^i}{i!} = \sum_{i=0}^n (-1)^i{n \choose i}i^{n-i} (i-1)^i$$

I can't figure out how to transform from one to the other but numerically they seem to be the same series.

• What sequence are you looking to generate, exactly? – preferred_anon Mar 21 '14 at 13:48
• I am looking for the closed-form soluion to the sum. – anthonybell Mar 21 '14 at 13:53
• Are you sure it's written correctly? You seem to be missing an obvious simplification. – user14972 Mar 21 '14 at 13:56
• The series is $\{\sum_{i=0}^n {n \choose i}i^i (i-1)^{n-i}\}_{n=0}^{\infty}$ – anthonybell Mar 21 '14 at 13:58
• What don't you simplify $i^ii^{n-i}=i^n$ ? From there, the solution follows easily. – Tom-Tom Mar 21 '14 at 13:58

Remove the terms $i=0$, they sum up to $\mathrm e^{-x}$ and the terms $i=1$ which sum up to $x$. Perform first the sum over $n$ using $$\sum_{n=0}^\infty\binom nk \frac{x^n}{n!}=\frac{\mathrm e^xx^k}{k!}$$ you then get $$F(x)-x-\mathrm e^{-x}=\sum_{n=0}^\infty\sum_{k=2}^\infty\binom nk\left(\frac k{k-1}\right)^k(k-1)^n\frac {x^n}{n!}=\sum_{k=2}^\infty\left(\frac k{k-1}\right)^k\frac{\mathrm e^{(k-1)x}[(k-1)x]^k}{k!}$$ A simplification gives $$F(x)=x+\mathrm e^{-x}+\mathrm e^{-x}\sum_{k=2}^\infty\frac{k^k}{k!}\left(x\mathrm e^x\right)^k.$$ You can relate this to the Lambert W function which is given by the series $$W(x)=-\sum_{k=1}^\infty \frac{k^{k-1}}{k!}(-x)^k.$$ So you can write $$F(x)=x\,W'(-x\mathrm e^x)+\mathrm e^{-x}.$$
• anthonybell's edit (after correcting the left side to alternating sign) is asking for the subfactorial numbers en.wikipedia.org/wiki/Derangement $(-1)^n \text{Subfactorial}[n]=(-1)^n n! \sum _{i=0}^n \frac{(-1)^i}{i!}=\sum _{i=0}^n (-1)^i (i-1)^i i^{n-i} \binom{n}{i}=(-1)^n \text{Round}\left[\frac{n!}{e}\right]$ – Wouter M. Mar 21 '14 at 18:18