Expected number of nodes of degree $1$ in binary tree with $n$ edges

Question

What is the expected number of nodes of degree 1 in a binary tree with $n$ edges? The binary tree need not be full; 1 child node is allowed.

I have looked at Catalan numbers. These can give you the total number of full binary trees with $n$ internal nodes. However, it doesn't seem they can give any answers for the case of binary trees that allow nodes to have 1 child.

I have also read in detail "Enumeration of Ordered Trees" which solves for the general case (any number of children nodes):

1. The number of trees with $k$ leaves.
2. The number of nodes of degree $d$ in those trees.
3. The number of trees with a root of degree $r$
4. The number of nodes of degree $d$ on level $l$ in these trees.

However, these results are insufficient as they are overly general. I am only interested in binary trees (0-2 children nodes).

Two ingredients that could answer my question would be:

1. The number of general binary trees with $n$ edges.
2. The number of nodes of degree $1$ in those trees.

Then the expected number of nodes with degree $1$ is the division of these. This is a related question: Counting the number of rooted $m$-ary trees., though it does not seem to answer this.

Thank you in advance for any resources you could direct me to.

Answer 1

Consider a tree $T$ with a marked vertex $v$. This tree can be uniquely decomposed into two trees: a subtree $T_1$ rooted at $v$ and the remaining subtree $T_2$ in which $v$ is a leaf (a vertex of degree $1$).

Translating this into (ordinary) generating functions, let $V=V(x)$ be the generating function for binary trees with a marked vertex, $L=L(x)$ be the generating function for binary trees with a marked leaf, and $T=T(x)$ be the generating function for binary trees. Then $$V=LT,$$ i.e. $$L=\frac{V}{T}.$$

If $T$ has coefficient sequence $\{a_n\}$, then $V$ has coefficient sequence $\{na_n\}$, i.e. $V=xT'$. Therefore, $$L=\frac{xT'}{T}.$$

Catalan numbers also count binary trees where nodes may have $1$ child (i.e. a left child or a right child). To see this, take any full binary tree and delete all leaves.

We are counting binary trees with $n$ edges, i.e. with $n+1$ vertices. Their ordinary generating function is $$T=\dfrac{C-1}{x}=C^2,$$ where $C=C(x)$ is the generating function for Catalan numbers. Thus, $T'=2CC'$.

To find $C'$, differentiate $C=1+xC^2$ implicitly to get $C'=C^2+2xCC'$, so $$C'=\frac{C^2}{1-2xC}=BC^2,$$ where $B=B(x)=\dfrac{1}{\sqrt{1-4x}}=\dfrac{1}{1-2xC}$ is the generating function for the central binomial coefficients.

Thus, $$L=\frac{x\cdot2CC'}{C^2}=\frac{2xBC^2}{C}=2xBC=B-1.$$

Let $[x^n]f(x)$ denote the coefficient of $f(x)$ at $x^n$. Then the expected value we need is $$ \frac{[x^n](B-1)}{[x^n]C^2}=\frac{(n+1)C_n}{C_{n+1}}=\frac{\binom{2n}{n}}{\frac{1}{n+2}\binom{2n+2}{n+1}}=\frac{(n+2)(n+1)^2}{(2n+2)(2n+1)}=\frac{(n+2)(n+1)}{2(2n+1)}. $$