2
$\begingroup$

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.

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

Here's a computation using the exponential generating function.

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}.$$

$\endgroup$
  • $\begingroup$ 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]$ $\endgroup$ – Wouter M. Mar 21 '14 at 18:18
  • $\begingroup$ The main question produces, like Sabyasachi said : {1,0,5,38,497,8084,160597,3763626,101666497,3110368328,106303240901} using Table[Sum[Binomial[n, i] w^i (w-1)^(n-i) /. w -> i, {i, 0, n}], {n, 0, 10}] (* remark the little dance around the 0^0 issue *) I have trouble matching this to V. Rosetto's answer, which produces {1, -2, -7, -73, -895, -14401, -283391, -6598145, -177373183, -5406289921, -184223743999 } $\endgroup$ – Wouter M. Mar 21 '14 at 18:19
  • $\begingroup$ Yes, the left side is a solution to a problem which can be cast as a derangement and the right side is a solution to the same problem using the principle of inclusion and exclusion. I wanted to prove that they both produce the same answer. $\endgroup$ – anthonybell Mar 22 '14 at 18:54

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.