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.