6
$\begingroup$

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!)

$\endgroup$
  • $\begingroup$ What happens if you try to compute the Taylor series for $y$ (using implicit differentiation) around $x=0$? Using Stirling's approximation, it looks like you've got a reasonably convergent power series around $x=0$. $\endgroup$ – Michael Burr Mar 6 '17 at 15:15
  • 1
    $\begingroup$ This is $y=W(-x)$ where $W$ is the Lambert W function. $\endgroup$ – Thomas Andrews Mar 6 '17 at 15:17
  • $\begingroup$ Do you mean differentiate with respect to $x$ to get $(y' - yy')e^{-y} = 1$, ie $(1 - y)y' e^{-y} = 1$? I don't really see how this helps: yes we can try differentiating under the sum, but there still $(sum)^{-(sum)'}$ which is awkward. $\endgroup$ – Sam T Mar 6 '17 at 15:19
  • $\begingroup$ @ThomasAndrews yeah, I saw that when looking up related questions. I can't see any explicit formulation of the Lambert W function -- in fact, one person said "use the Lambert W function, as an explicit solution is very complicated" (or something to that effect). Above I've given an explicit formula in the form of a power series with very nice coefficients. $\endgroup$ – Sam T Mar 6 '17 at 15:21
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Superb, thanks! Could you explain a little further why the term $X \cdot T^k(x)/k!$ is the generating function you've claimed? In the pair $(v,F_k)$, I presume $F_k$ can be a $k$-tuple of trees of any size? But then what if $v$ is in one of these trees but not the root, and adding the edge you suggested creates a cycle? $\endgroup$ – Sam T Mar 6 '17 at 17:11
  • $\begingroup$ See here for a note on products of generating functions. In particular, the product $T^k(x)$ is the exponential generating function for an ordered $k$-tuple of rooted trees. So $T^k(x)/k!$ is the exponential generating function for number of forest of $k$ trees. $\endgroup$ – D Poole Mar 7 '17 at 19:42
  • $\begingroup$ Ok, thanks for that. Probably being slow (10pm makes me like that!), but I don't see why multiplying by $x$ then adds in $v$. Informally, the division by $k!$ changes $F_k$ from ordered to unordered, correct? $\endgroup$ – Sam T Mar 7 '17 at 22:09
  • $\begingroup$ Correct. Also $x = 0 \cdot x^0 + 1 \cdot x^1 + 0 \cdot x^2 + 0 \cdot x^3 +...$ is the generating function for number of trees with a single vertex. I.e. there is only one such tree. You can create a bijection between rooted trees (with deg of root $k$) with unions of a single vertex with a forest of $k$ rooted trees. $\endgroup$ – D Poole Mar 13 '17 at 17:59
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yeah, Lambert is noted in the comments. I haven't been able to find anywhere that the Lambert function has the Taylor series that I've written above... $\endgroup$ – Sam T Mar 6 '17 at 15:31
  • $\begingroup$ Search for asymptotic expansions in the Wiki page (en.wikipedia.org/wiki/Lambert_W_function) $\endgroup$ – MrYouMath Mar 6 '17 at 15:32
  • $\begingroup$ Wikipedia gives the Taylor series above for Lambert, but doesn't prove it. @SamT $\endgroup$ – Thomas Andrews Mar 6 '17 at 15:42
  • $\begingroup$ @ThomasAndrews The Taylor series can be obtained by the Lagrange inversion theorem, the link is in my answer. The page also contains the derivation. $\endgroup$ – MrYouMath Mar 6 '17 at 15:43
  • $\begingroup$ Yes, I've just seen the part. The bit that I was missing was to do with the alternating signs on the Wiki page -- but of course, the answer is $y = -W(-x)$, so the signs cancel out nicely. \\ Working out those coefficients would be a nightmare though! $\endgroup$ – Sam T Mar 6 '17 at 15:47
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yeah, so differentiating twice isn't a bad shout: it means we can cancel the exponentials. However, I don't see how you deduce $y''(x) = 2$. You have this nasty $(dy/dx)^2$ term in there. I'll have a little more of a think... $\endgroup$ – Sam T Mar 6 '17 at 15:29
  • $\begingroup$ $\left(\frac{dy}{dx}\right)^2$ is the square of the first derivative, which we know is $1$. $\endgroup$ – Michael Burr Mar 6 '17 at 15:51
  • $\begingroup$ Oh, I see, you're looking for the Taylor expansion about $0$, and hence are considering $y'(0)$. I see. I guess doing this way is just a special case of the Lagrange inversion for this particular situation. $\endgroup$ – Sam T Mar 6 '17 at 16:05

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.