Show $y = \sum_{k=1}^\infty \frac{k^{k-1}}{k!} x^k$ satisfies $ye^{-y} = x$.

Question

My question is literally the title:

Show $y = \sum_{k=1}^\infty \frac{k^{k-1}}{k!} x^k$ satisfies $ye^{-y} = x$.

---

Here's a little motivation for the question. If you don't care about motivation, then ignore what follows!

Considering Erdos-Renyi random graphs, in the supercritical case $p = c/n$ with $c > 1$, and consider the size of the giant component. We can show (eg Grimmett, Probability on Graphs, Theorem 11.1) that the size is $\theta(p) n$, where $\theta(p) \equiv \theta(c)$ is the survival probability for a Poisson$(c)$ branching process ($p = c/n$), and this satisfies $$ 1 - \theta(c) = \frac{1}{c} \sum_{k=1}^\infty \frac{k^{k-1}}{k!} (ce^{-c})^k.$$ Moreover, one can also show (eg, Frieze-Karonski, Introduction to Random Graphs, Theorem 2.14) that $\theta(c) = 1 - c'/c$, where $c'$ is the conjugate of $c$, ie for $c>1$ it is the solution $c' < 1$ of $c'e^{-c'} = c e^{-c}$. Combining these two formulae, we obtain (cancelling the $1/c$ factor) $$ c' = \frac{1}{c} \sum_{k=1}^\infty \frac{k^{k-1}}{k!} (ce^{-c})^k.$$ In my general statement at the top, I've just let $y = c'$ and $x = ce^{-c}$ for notational convenience.

---

Try as I might, I haven't been able to come up with any way of justifying the equality, however -- other than, of course, proving the two results on the size of the giant separately, then equating. One would hope that there's a way of showing it directly -- after all, it's not exactly an ugly expression: after not very long it becomes basically geometric; I tried on Matlab and with $c = 3$ I get machine precision after only $40$ terms in the sum. (My PhD supervisor has had a look at it too, but she wasn't able to work it out either!)

Answer 1

Here is a combinatorial way to view this identity with generating functions.

The number of labelled unrooted trees with vertex set $[n]:=\{1, \ldots, n\}$ is $n^{n-2}$ (Cayley's formula). So the number of rooted trees is $\alpha_n := n\cdot n^{n-2} = n^{n-1}$. So $y = T(x) := \sum_{n=1}^{\infty} \frac{\alpha_n}{n!} x^n$ is the (exponential) generating function for the sequence $\alpha_n$, of the number of rooted trees.

The identity you want can be written $$ T(x) = x \cdot e^{T(x)} = x \left(1+ T(x) + T^2(x)/2!+T^3(x)/3!+\ldots \right). $$

So you want to show that the coefficient by $x^n/n!$ on the right hand side is also $\alpha_n$. Obviously, $\alpha_n = \sum_{k=0}^\infty \alpha_n(k)$, where $\alpha_n(k)$ is the number of rooted trees where the root has degree $k$ ($\alpha_n(k) = 0$ for $k \geq n$).

The term $x \cdot T^k(x)/k!$ is the generating function for the number of ordered pairs of $(v, F_k)$ where $v$ is a single vertex and $F_k$ is an unordered $k$-tuple of disjoint rooted trees. Now there is a natural bijection between such a pair and rooted trees (connect single vertex (the new root) with each root in $k$-tuple) where the root has degree $k$. In particular, the coefficient in front of $x^n/n!$ in $x \cdot T^k(x)/k!$ is the number of rooted trees on $n$ vertices where the root has degree $k$. That is, the coefficient is $\alpha_n(k)$.

Answer 2

Hint: Substitute $u=-y$ then $-ue^{u}=x \implies ue^u=-x$, hence $u=W(-x)$, in which $W$ is the Lambert function. Use Lagranges inversion theorem to derive its Taylor series. Or simply look it up on the wiki page under asymptotic expansions. Note, that this equality is only true in the region of convergence.

Answer 3

Idea (not completely worked out, but too long for a comment):

• When $x=0$, $y=0$ because exponentials are never zero.

• Using implicit differentiation, $\left(e^{-y}-ye^{-y}\right)\frac{dy}{dx}=1$ using implicit differentiation. Since $y=0$, $\frac{dy}{dx}=1$.

• Using implicit differentiation again, we have $$ \left(-2e^{-y}+ye^{-y}\right)\left(\frac{dy}{dx}\right)^2+\left(e^{-y}-ye^{-y}\right)\frac{d^2y}{dx^2}=0 $$ Substituting in our known values, you get $\frac{d^2y}{dx^2}=2$.

Observe that when these are plugged into the Taylor expansion for $y$ (dividing by $k!$), you get the first few terms in your formula. There's a lot of structure in these implicit derivatives, you should be able to get some sort of recurrence to explicitly solve.