Number of nodes with even offspring I've been working on a combinatorics assignment, and while the last few questions had clever solutions which didn't involve functional equations and the use LIFT, I fear I'm at my end.
Given a Planted Tree $\ T$ with $n$ nodes let $h(T)$ be the number of nodes in $T$ with an even number of children. In particular, this includes the leaves. Find the average value of $h(T)$ among all PTs with $n$ nodes.
So far I've tried computing the value of $h(T)$ summed over PTs with $n$ nodes and sticking that into OEIS. While it seems to follow an exponential generating function, we haven't done those yet in class. Moreover the value I got for trees with 6 nodes differs, being 158 instead of 166, though that might easily be human error. Though I don't see how this will help me, even if it's true.
I then tried to write out a functional equation from a recursive formula. I ran into trouble when defining the weight function $h(T)$ recursively. I tried 
$$ h(T) = \frac{1}{2}(1+(-1)^d) + \sum_{i=1}^{d}h(T_{d}) $$
It's not hard to see where the fails. The sum
$$ \sum_{T\in PT_{n}}x^{h(T)} $$
Won't even converge when you substitute $T=\{root, T_{1}, ... ,T_{d}\}$
So I'm stuck. Any help would be appreciated.
EDIT: I already know the number of PTs with n nodes. Which is why I'm so focused on finding the number of nodes with an even number of children across all PTs with n nodes.
 A: Here  is some  enrichment material  to complete  this  calculation.  I
assume  you  are working  with  labeled  trees  since you  mention  an
exponential generating function.  First  note that these planted trees
correspond to ordinary rooted trees with an extra node attached at the
root.
The combinatorial class equation here is
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{T} = 
\mathcal{Z} \times \textsc{SET}(\mathcal{T}).$$
This gives the functional equation
$$T(z) = z \exp T(z)$$
from which Lagrange inversion produces
$$n! [z^n] T(z) = n^{n-1}.$$
Now if we wish to mark nodes with an even number of children
we get
$$\mathcal{T} = 
\mathcal{Z} \times \mathcal{U} \times \textsc{SET}_\mathrm{even}(\mathcal{T})
+ \mathcal{Z} \times \textsc{SET}_\mathrm{odd}(\mathcal{T}).$$
Introduce $Q(z, u)$ for this specification so that $Q(z,1) = T(z).$ We
obtain the functional equation
$$Q(z) = uz \sum_{k\ge 0} \frac{Q(z)^{2k}}{(2k)!}
+ z \sum_{k\ge 0} \frac{Q(z)^{2k+1}}{(2k+1)!}.$$
Now  to count  the number  of nodes  with an  even number  of children
introduce
$$G(z) = \left. \frac{\partial}{\partial u} Q(z, u) \right|_{u=1}.$$
Differentiate  the functional  equation with  respect to  $u$  and put
$u=1$ to obtain
$$G(z) = z \sum_{k\ge 0} \frac{T(z)^{2k}}{(2k)!}
+ z \sum_{k\ge 1} \frac{T(z)^{2k-1}}{(2k-1)!} G(z)
+ z \sum_{k\ge 0} \frac{T(z)^{2k}}{(2k)!} G(z).$$
This yields
$$G(z) = z \sum_{k\ge 0} \frac{T(z)^{2k}}{(2k)!} 
+ z \times G(z)\exp T(z)$$
which is
$$G(z) = \frac{1}{2} z (\exp T(z) + \exp(-T(z)) + G(z) T(z)$$
or $$G(z) = \frac{1}{2} T(z) + \frac{1}{2} \frac{z^2}{T(z)}
+ G(z) T(z).$$
This finally produces
$$G(z) = \frac{T(z)^2+z^2}{2T(z)(1-T(z))}.$$
Now to extract coefficiets from this we use the Cauchy Coefficient Formula.
Start from
$$n! [z^n] G(z) = 
\frac{n!}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n+1}} \frac{T(z)^2+z^2}{2T(z)(1-T(z))}  \; dz.$$
There are two components here. 
First component.
Put $T(z)=w$ so that $z=w/\exp(w) = w\exp(-w)$
and $dz = (\exp(-w) - w\exp(-w)) \; dw$
to get
$$\frac{n!}{2\pi i}
\int_{|w|=\epsilon}
\frac{\exp(w(n+1))}{w^{n+1}}
\times 
\frac{w^2}{2w(1-w)}
\times (\exp(-w) - w\exp(-w)) \;  dw
\\ = \frac{1}{2} \frac{n!}{2\pi i}
\int_{|w|=\epsilon}
\frac{\exp(wn)}{w^n} \;  dw 
= \frac{1}{2} n! \frac{n^{n-1}}{(n-1)!}
= \frac{1}{2} n^n.$$
Second component.
Using the same substitution we obtain
$$\frac{n!}{2\pi i}
\int_{|w|=\epsilon}
\frac{\exp(w(n+1))}{w^{n+1}}
\times 
\frac{w^2\times \exp(-2w)}{2w(1-w)}
\times (\exp(-w) - w\exp(-w)) \;  dw
\\ = \frac{1}{2} \frac{n!}{2\pi i}
\int_{|w|=\epsilon}
\frac{\exp(w(n-2))}{w^n} \;  dw
= \frac{1}{2} n! \frac{(n-2)^{n-1}}{(n-1)!}
= \frac{1}{2} n\times (n-2)^{n-1}.$$
This gives the following sequence:
$$1, 2, 15, 144, 1765, 26400, 466459, 9508352,
\\ 219651849, 5671088640, \ldots $$
Conclusion. The average number of even outdegree nodes
among the labeled trees on $n$ nodes is
$$\frac{1}{n^{n-1}} \times
\frac{1}{2} \left(n^n + n \times (n-2)^{n-1}\right)$$
which yields
$$\frac{1}{2} n 
+ \frac{1}{2} \frac{(n-2)^{n-1}}{n^{n-2}}.$$
To get the asymptotics re-write this like so:
$$\frac{1}{2} n 
+ \frac{1}{2} \times n \times \frac{(n-2)^{n-1}}{n^{n-1}}
= \frac{1}{2} n 
+ \frac{1}{2} \times n \times \left(1-\frac{2}{n}\right)^{n-1}.$$
This gives
$$\frac{1}{2} \times n \times \left(1+\frac{1}{e^2}\right).$$
There is a bias towards even-degree nodes.
This was also seen at this
MSE link
where unlabeled trees were studied.
Remark. These data were verified for small $n$ with the combstruct package.

with(combstruct);

gf :=
proc(n)
    option remember;
    local trees, evens;

    trees := { T= Union(Z, Prod(Z, Set(T, card >=1 ))),
               Z=Atom };

    evens :=
    proc(struct)
        local rval;

        if type(struct, function) then
            if op(0, struct) = Prod then
                return evens(op(2, struct))
            else
                rval := add(evens(op(q, struct)),
                            q=1..nops(struct));

                if type(nops(struct), even) then
                    return 1+rval;
                fi;

                return rval;
            fi;
        fi;

        return 1;
    end;

    add(u^evens(t), t in allstructs([T, trees, labeled], size=n));
end;

TGF := solve(T=z*exp(T), T);

q :=
proc(n)
    option remember;

    n!*coeftayl((TGF^2+z^2)/2/TGF/(1-TGF), z=0, n);
end;

