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

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.

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)}.$$

• Fantastic, thank you so much! This is quite helpful. Jul 30, 2020 at 18:10