1
$\begingroup$

How to prove that: $$ \frac{W(x)}{xe^x}=\sum_{n=0}^{\infty} \frac{(-1)^n}{n!}T(n)x^n $$ where $T(n)$ counts the number of forests of rooted labeled trees using labels in a subset of $\{1,\ldots,n\}$ and $W(x)$ is the Lambert $W$ function?

Also, as shown in this video at 6:54, does $T (n)=n^{n-2} $ ?

$\endgroup$
3
$\begingroup$

Start by making some definitions. The combinatorial class $\mathcal{T}$ of labelled trees has the specification

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{T} = \mathcal{Z} \times \textsc{SET}(\mathcal{T})$$ which gives the functional equation $$T(z) = z \exp T(z).$$

We have by Cayley that
$$T(z) = \sum_{n\ge 1} n^{n-1} \frac{z^n}{n!}.$$

We seek to prove that

$$\bbox[5px,border:2px solid #00A000]{ W(z) = z \exp(z) \sum_{n\ge 0} (-1)^{n} Q_n \frac{z^n}{n!}}$$

where $Q_n$ is the number of rooted subtrees for a fixed root in the complete graph $K_{n+1}$ on $n+1$ vertices. These have from $k=0$ to $k=n$ nodes not including the fixed root and represent a forest that is attached to the root. (Specification as in OEIS A088957, example given by A. Chin.) The combinatorial class $\mathcal{F}$ of forests is given by

$$\mathcal{F} = \textsc{SET}(\mathcal{T})$$

and hence has EGF

$$F(z) = \exp T(z) = \frac{1}{z} T(z).$$

We also have by construction that

$$Q_n = \sum_{k=0}^{n} {n\choose k} k! [z^k] F(z).$$

Here we chose the labels that go into the forest and substitute them into the forest respecting the ordering of the nodes in the source forest. It follows by convolution of EGFs that (recall that $n! [z^n] \exp(z) = 1$)

$$Q(z) = \sum_{n\ge 0} Q_n \frac{z^n}{n!} = \exp(z) \frac{1}{z} T(z).$$

Now by definition the principal branch of the Lambert W function is

$$W(z) = \sum_{n\ge 1} (-1)^{n-1} n^{n-1} \frac{z^n}{n!}$$

and hence we obtain

$$\bbox[5px,border:2px solid #00A000]{ \sum_{n\ge 0} Q_n \frac{z^n}{n!} = \frac{1}{z} T(z) \exp(z) = - \frac{1}{z} W(-z) \exp(z).}$$

The claim now follows by replacing $z$ by $-z$ to get

$$\sum_{n\ge 0} (-1)^n Q_n \frac{z^n}{n!} = \frac{1}{z} W(z) \exp(-z).$$

$\endgroup$
3
$\begingroup$

This is not an answer.

This is a problem of Taylor series composition using $$W(x)=\sum_{n=1}^\infty (-1)^n\,\frac{n^{(n-1)}}{n!}x^n$$ (have a look here) $$e^{-x}=\sum_{n=0}^\infty (-1)^n\,\frac{x^n}{n!}$$ So, computing the first terms, we have, as a series, $$\frac{W(x)}{xe^x}=1-2 x+3 x^2-\frac{29 x^3}{6}+\frac{53 x^4}{6}-\frac{2117 x^5}{120}+\frac{2683 x^6}{72}-\frac{82403 x^7}{1008}+O\left(x^8\right)$$ making the $T_n$ to be the sequence $$\{1,2,6,29,212,2117,26830,412015\}$$ which is sequence $A088957$ in $OEIS$.

In a comment, Alex Chin wrote that these coefficients are "the number of rooted subtrees (for a fixed root) in the complete graph on $n$ vertices" (please : do not ask me what this means !).

$\endgroup$