0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Fantastic, thank you so much! This is quite helpful. $\endgroup$ – Miles Jul 30 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.