Number of even rooted trees

Question

An even tree is a rooted tree such that every vertex has an even number of successors. Clearly, an even tree has an odd number of vertices. Let $g(2n+1)$ be the number of even trees with $(2n+1)$ vertices.

The exercise 139 chapter 1 of Stanley's Combinatorics chapter 1 asks to express $g(2n+1)$ in terms of Euler numbers, and it suggests using generating functions. I read the solution, but I can't understand the following step. He basically defines $$z=\sum_{n\geq 1} g(n)\frac{x^n}{n!}.$$ Here I am assuming $g(2n)=0$. Then the author states without further justification that $$z'=1+\frac{z^2}{2!}+\frac{z^4}{4!}+\cdots $$ I really don't understand this step. Could you help me?

Answer 1

You're missing an important part of the question: $g(2n+1)$ is the number of increasing labelled even rooted trees on $2n+1$ vertices, meaning that the vertices are labelled (bijectively) by $[2n+1]$ and every path from the root down has the labels increasing. An important observation is that the root always receives label $1$.

To see the recursion behind the differential equation of the exponential generating function, notice that we can break up any such tree into $2k$ subtrees of the root which are each themselves increasing even rooted trees, now with labels coming from $[2,2n+1]$. We have $g(a_i)$ choices for the $i$th subtree, where $a_1+\cdots+a_{2k}=2n$, and we need to partition the $2n$ labels among the subtrees, which is done in $$ \frac{(2n)!}{a_1!\cdots a_{2k}!} $$ ways. We have overcounted, since the subtrees themselves are indistinguishable, so we must divide by $(2k)!$. Thus $$ g(2n+1) = \sum_{k \geq 0} \frac{1}{(2k)!} \sum_{a_1+\cdots+a_{2k}=2n} \frac{(2n)!}{a_1!\cdots a_{2k}!} g(a_1) \cdots g(a_{2k}) $$ $$ = \sum_{k \geq 0} \frac{(2n)!}{(2k)!} [x^{2n}] \left( \sum_{a \geq 0} g(a) \frac{x^a}{a!} \right)^{2k} ,$$ and hence $$ \sum_{n\geq 0} g(2n+1) \frac{x^{2n}}{(2n)!} = \sum_{k\geq 0} \frac{1}{(2k)!} \left( \sum_{a\geq 0} g(a) \frac{x^a}{a!} \right)^{2k} .$$ Recognizing the left side as the derivative of the exponential generating function $z(x) = \sum g(a) x^a/a!$, we get $z' = \cosh(z)$ as desired.

The key here is realizing that although there are $2n+1$ labels, only $2n$ get distributed to the sub-objects, and so the derivative takes care of this change in index. As you get better with generating functions, you will be able to do many of the steps quickly: use EGFs because of the labels, recurse on the even number of subtrees of the root, divide by factorial because subtrees are indistinguishable, and finally note that one label is fixed causing a change of index which is done by a derivative.

Answer 2

Hint: Reading the answer to this problem, there might also be some kind of notation trap that OP might have some problems with.

(The answer verbatim by R. P. Stanley): Let $z=\sum_{n\geq 1}g(n)x^n/n!$. Then $z^\prime=1+\frac{1}{2}z^2+\frac{1}{4!}z^4+\cdots=\cosh(z)$. The solution to this differential equation satisfying $z(0)=0$ is \begin{align*} z(x)=\log(\sec x+ \tan x). \end{align*} Since $z^{\prime}(x)=\sec x$, it follows easily that $g(2n+1)=E_{2n}$.

Here we could mix up notation and read instead of the given expression something like \begin{align*} z^{\prime}(x)=1+\frac{1}{2}x^2+\frac{1}{4!}x^4+\cdots=\cosh(x) \end{align*} But in fact we have \begin{align*} \color{blue}{z^{\prime}(x)=1+\frac{1}{2}z^2(x)+\frac{1}{4!}z^4(x)+\cdots=\cosh(z(x))} \end{align*}