2
$\begingroup$

The question is about number of trees, where all internal nodes (total number denoted as $n$) have degree 2 except of some ($k$) nodes with degree 1. Let's denote the total number of such trees as $F(n,k)$.

It's known that $F(n,0) = C_n$, where $C_n$ is $n$-th Catalan number.

It seems (after some counting experiments using computer) that $F(n,k) = C_{n-k}\cdot C(2n-k,k)$ where the second multiplicand is binomial coefficient. (Of course, if I've not made any mistake.)

I can't get my brain around this fact for now, but it seems that there should be some nice and simple interpretation, based on combinatorics. If you can point to some resource (or maybe post an answer), I would be very grateful. :)

(I will think more seriously about this, most probably, only on weekend - because of busy next workdays. If no answers until then, I will try to find it and post it myself.)

$\endgroup$
1
  • 2
    $\begingroup$ The idea will be that such a tree could be uniquely "grown" from a "strictly binary" tree with $n-k$ internal nodes by a process of picking an internal edge and expanding it to an edge-node-edge triple. $\endgroup$ Commented Jun 18 at 22:24

2 Answers 2

5
$\begingroup$

Let $T(n,k)$ be the set of trees of size $n$ such that $n-k$ internal nodes have exactly two children while $k$ internal nodes have exactly one children. Let $T(n)$ be the set of binary trees of size $n$.

We can send a tree $T \in T(n,k)$ to a tree $T' \in T(n-k)$ by "collapsing" all the internal nodes with only one child. This defines a function $f : T(n,k) \to T(n-k)$. Take some $T' \in T(n-k)$ and add a single "dangling" edge to the root. What you have now is not a tree, but it does have $2(n-k)+1$ edges. By adding $k$ new nodes to these edges, you obtain a tree in $T(n,k)$. It is clear that any $T$ such that $f(T) = T'$ must be obtainable from $T'$ in this way. Seeing the edges as buckets and the $k$ nodes we want to place on them as balls, it is well known that the number of ways to do that is $C(2n-k,k)$.

Hence for any $T' \in T(n-k)$, the fiber $f^{-1}(T')$ consists of $C(2n-k,k)$ elements. The fibers always partition the domain. Therefore $$F(n,k) = |T(n,k)| = C(2n-1,k)\cdot |T(n-k)| = C_{n-k}\cdot C(2n-k,k).$$

$\endgroup$
2
$\begingroup$

I will add a generating function method (using the symbolic method).

Let $G(z,u)$ be the generating function for this class, where $z$ enumerates the number of internal nodes and $u$ the number of nodes with 1 child.

This sort of tree is a single leaf or a root with either $1$ or $2$ trees as children. We get the generating function equation

$$ G = 1 + z(uG+G^2) $$

which gives (we choose the minus sign, since that is good at $z=0$)

$$ G(z,u) = \frac{1-uz-\sqrt{(1-uz)^2-4z}}{2z} $$

Use the binomial theorem to expand. When $n>0$ (so we can ignore the $1-uz$ -part)

$$ [z^nu^k]G(z,u) \\ = -\frac{1}{2} [z^{n+1}u^k] \sqrt{(1-uz)^2-4z} \\ = -\frac{1}{2} [z^{n+1}u^k] \sum_{j=0}^\infty \binom{\frac{1}{2}}{j}(1-uz)^{2\left(\frac{1}{2}-j\right)}(-4z)^j \\ = -\frac{1}{2} [z^{n+1}u^k] \sum_{j=0}^\infty \binom{\frac{1}{2}}{j} \sum_{m=0}^\infty \binom{1-2j}{m} (-uz)^m (-4z)^j \\ = -\frac{1}{2} \binom{\frac{1}{2}}{n+1-k} \binom{1-2(n+1-k)}{k}(-1)^k(-4)^{n+1-k} $$

I was too lazy to check how it simplifies to $C_{n-k} \binom{2n-k}{k}$ but it is true: Desmos calculation.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .