Number of non-planar increasing labeled trees

53 Views Asked by At

I want to calculate the number of non-planar increasing labeled trees with generating functions. Where increasing means that the labels of a path starting at the root form an increasing sequence of numbers and non-planar means that the order in which the subtrees are attached to the root doesn't matter.

My first idea how to approach this exercise was to use the box product, which is defined by

$$C=A^{\square}*B,$$ $$\hat{C}(x)=\int\limits_0^x \hat{A}'(t)B(t)dt.$$

Where A and B are labeled combinatoric structures for which the ordered pair $(\alpha,\beta)$ with $\alpha\in A$, $\beta\in B$ and $\alpha$ is labeled with $1$. $\hat{A}(x)$ and $\hat{C}(x)$ are the exponential generating functions respectively.

I know that the planar labeled trees $M$ satisfy the recursion $$M=\{\circ\}*e^M$$ and my idea was to describe the increasing labeled trees by $$C=\{\circ\}^\square * e^C.$$ It follows that $\hat{C}'(x)=e^{C(x)}$, but when writing both sides as formal power series explicitly I couldn't find a way to derive the coefficients of $C(x)$.