Mysterious series involving $ k^{k-1}$

Question

What is the trick to show that $$\sum_{k=1}^{\infty} \frac{k^{k-1}}{k!}e^{-k} = 1$$ I am struggling to find the method...

Answer 1

This is a special value of (the principal branch of) the Lambert W function:

$$-W(-x)=\sum_{k=1}^{\infty} \frac {k^{k-1}}{k!}x^k$$

Indeed, your expression is precisely $$-W\left(-\frac 1e\right)$$ and it is easily seen that $$W\left(-\frac 1e\right)=-1$$

Answer 2

(This is a cummunity-wiki answer migrated from a thread that was deleted as a duplicate.)

---

Note that the Lambert W-function admits the Maclaurin series

$$ W(x) = \sum_{n=1}^{\infty} \frac{(-n)^{n-1}}{n!} x^n, \qquad |x| \leq e^{-1}. $$

Plugging $x = -e^{-1}$ and rearranging, we obtain

$$ \sum_{n=1}^{\infty} \frac{n^{n-1}}{n!} e^{-n} = -W(-e^{-1}) = 1.$$

---

A slightly different proof is as follows: From the Cayley's formula, $n^{n-1}$ is the number of rooted labeled trees with $n$ vertices. Now let $\mathcal{T}$ denote the combinatorial class of all rooted labeled trees. Then its EGF (exponential generating function) is given by

$$ T(z) = \sum_{\alpha\in\mathcal{T}}\frac{z^{|\alpha|}}{|\alpha|!} = \sum_{n=1}^{\infty} \frac{n^{n-1}}{n!} z^n. $$

Now note that this class admits the specification

$$ \mathcal{T} = \{\text{root}\} * \mathrm{S{\small ET}}(\mathcal{T}), $$

reflecting the fact that each rooted labeled tree can be decomposed into the root and rooted subtrees. So, $T(z)$ must solve the functional equation

$$ T(z) = z e^{T(z)}. $$

This is originally an equality between formal power series, but since $T(z)$ converges for $|z| \leq e^{-1}$, the equality continues to hold as functions on this disk of convergence. So, plugging $z = e^{-1}$ and writing $w = T(e^{-1})$, we have

$$ w = e^{w - 1}, $$

and the unique real solution of this equation is $ w = 1 $.