Lemma: Conditioning probability and height recursion

For odd $N$,

Define

Then

For a fixed $N$, the coefficients required in these formulas depend only on $p_0,\dots ,p_{N-1}$.

Proof. The offspring increments are at least $-1$. Among the $N$ circular shifts of a list totaling $-1$, exactly one is a valid tree exploration. Summing the iid probabilities gives the Otter–Dwass formula (eq:pi) Dwass. The increment law $\xi -1$ has lattice span two, mean zero, and variance ${\sigma }^2$. The finite-variance lattice local limit theorem at $-1$ yields the stated asymptotic.

A tree of height at most $L$ has a root and a sequence of children whose subtrees have height at most $L-1$. Multiplying their generating functions and averaging over root offspring gives $F_L=zP(F_{L-1})$. For $L=0$, this gives $F_0=p_{0}z$. Its coefficient of $z^N$ is therefore the unconditioned probability of total size $N$ and height at most $L$. Division by ${\pi }_N$ proves (eq:heighttail). A tree of $N$ nodes has no offspring number exceeding $N-1$.