An identity for rooted plane labelled trees

79 Views Asked by At

I wish to prove combinatorialy that

$$\frac{1}{1-\sum_{n=1}^{\infty} \frac{(n-1)^{n-1} z^n}{n!}} = \frac{T(z)}{z}$$ where $T(z)= \sum_{n=1}^{\infty} \frac{n^{n-1}z^n}{n!}$. $T(z)$ is the exponential generating function for rooted plane lebelled trees times $\frac{1}{z}$. Define $\mathcal{F}$ to be the combinatorial class so that $F_n = (n-1)^{n-1}$ then the exponential generating function for this class is $F(z) = \sum_{n=1}^{\infty}\frac{n^{n-1}z^n}{n!} $. Now it suffices to prove that $\text{SEQ}(\mathcal{F})$ is the exponential generating function for set of rooted plane labelled trees as $T(z)$ is known to satisfy $T(z)=ze^{T(z)}$.

Any hints would be appreciated.

1

There are 1 best solutions below

0
On

This can be understood using the fact that

Any parking function (counted by $(n+1)^{n-1}$) is a sequence of prime parking functions (counted by $(n-1)^{n-1}$).

See section 2 in the article https://arxiv.org/pdf/math/0312126.pdf for the statement, and the references [10] and [22] there for more details.