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.

  • $\begingroup$ What is "the compositional formula"? Is it another name for Riddell's formula? $\endgroup$ – 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)).$$


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


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


$$\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$$


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.