# labelled rooted tree with odd degree

Let $$F(z)$$ be the exponential generating function for labelled rooted trees with every vertex having even out-degree and let $$H(z)$$ be the exponential generating function for labelled rooted trees in which every vertex has odd degree.

How can I use the compositional formula to show that $$F(z) = \frac{z}{2}\left(e^{F(z)}+ e^{-F(z)}\right)$$ and then express $$H(z)$$ in terms of $$F(z)$$. Please, any help would be appreciated.

• What is "the compositional formula"? Is it another name for Riddell's formula? – Peter Taylor Nov 5 '18 at 8:37

For the first one we have from first principles using the notation from Analytic Combinatorics the combinatorial class equation

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{F} = \mathcal{Z} \times \textsc{SET}_{\text{even}}(\mathcal{F}).$$

We attach a set of even-outdegree trees of even cardinality at the root and obtain even out-degree at all nodes, recursively. For the second one observe that the elements of $$\mathcal{F}$$ have odd degree at all nodes except the root, hence we must attach an odd number of these to the root, getting

$$\mathcal{H} = \mathcal{Z} \times \textsc{SET}_{\text{odd}}(\mathcal{F}).$$

Note that

$$\textsc{SET}_{\text{even}}(\mathcal{Z}) = \textsc{SET}_{\text{=0}}(\mathcal{Z}) + \textsc{SET}_{\text{=2}}(\mathcal{Z}) + \textsc{SET}_{\text{=4}}(\mathcal{Z}) + \cdots$$

which gives the generating function

$$\frac{z^0}{0!}+\frac{z^2}{2!}+\frac{z^4}{4!}+\cdots = \frac{1}{2} (\exp(z)+\exp(-z)).$$

Similarly,

$$\textsc{SET}_{\text{odd}}(\mathcal{Z}) = \textsc{SET}_{\text{=1}}(\mathcal{Z}) + \textsc{SET}_{\text{=3}}(\mathcal{Z}) + \textsc{SET}_{\text{=5}}(\mathcal{Z}) + \cdots$$

this time with generating function

$$\frac{z^1}{1!}+\frac{z^3}{3!}+\frac{z^5}{5!}+\cdots = \frac{1}{2} (\exp(z)-\exp(-z)).$$

The conclusion is that

$$F(z) = z \frac{1}{2} (\exp(F(z)) + \exp(-F(z)) = z \cosh F(z)$$

and

$$H(z) = z \frac{1}{2} (\exp(F(z)) - \exp(-F(z)) = z \sinh F(z).$$

Solving these we get OEIS A036778 and OEIS A060279.

Remark. If we want to extract coefficients from $$F(z)$$ use the Cauchy Coeffcient Formula and write

$$F(z) = \sum_{n\ge 1} Q_n \frac{z^n}{n!}$$

to get

$$\frac{Q_n}{(n-1)!} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n}} F'(z) \; dz$$

We have

$$z = \frac{2F(z)}{\exp(F(z)) + \exp(-F(z))}$$

and put $$F(z) = w$$ so that $$F'(z) \; dz = dw$$ to obtain

$$\frac{Q_{n}}{(n-1)!} = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{2^{n} w^{n}} (\exp(w)+\exp(-w))^{n} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{2^{n} w^{n}} \sum_{p=0}^n {n\choose p} \exp(pw) \exp(-(n-p)w) \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{2^{n} w^{n}} \sum_{p=0}^n {n\choose p} \exp((2p-n)w) \; dw.$$

This is

$$Q_n = \frac{(n-1)!}{2^n} \sum_{p=0}^n {n\choose p} \frac{(2p-n)^{n-1}}{(n-1)!}$$

or

$$\bbox[5px,border:2px solid #00A000]{ Q_n = \frac{1}{2^n} \sum_{p=0}^n {n\choose p} (2p-n)^{n-1}.}$$

The sequence is

$$1, 0, 3, 0, 65, 0, 3787, 0, 427905, 0, 79549811, 0, \\ 22036379521, 0, 8513206310715, 0, 4374455745966593, \ldots$$