Recursive formula for a tree problem

Question

Question:

A binary is defined as a tree in which 1 vertex is the root, and any other vertex has 2 or 0 children. A vertex with 0 children is called a node, and a vertex with 2 children is called an inner vertex.

The order between the children is important.

A binary tree can be defined with recursion: a binary tree is one out of 2 options :

1. A single vertex.
2. A vertex in which two sub-trees, that were build before, are connected to him.

Now, let $D_n$ be the number of valid binary trees, >with $n$ inner vertices.

For this question, a binary tree is called $valid$ if for each inner vertex $v$, the left sub-tree connected to $v$ in the left side, contains an even amount (0,2,4,...) of inner vertices.

Find the recursive formula with starting conditions for $D_n$ such that the formula can use all values before. In addition, calculate $D_6$.

---

$Solution.$ in order to build a valid binary tree of size $n$ we can take all options for a valid binary tree of size $n-1$ and take all options for a valid binary tree of size $n-2$. Therefore, we get: $$D_n=D_{n-1}+D_{n-2}$$

For the starting conditions: we consider $D_1$ which is 1 because we have only the root, which has an even amount of inner vertices (0).

For $D_2$ we have the next tree:

Therefore, $D_2=1$.

Calculation for $D_6$: $$D_6=D_5+D_4=D_4+D_3+D_3+D_2=D_3+D_2+(D_2+D_1)\cdot 2 + D_2=D_2+D_1+D_2+2D_2+2D_1+D_2=5D_2 +3D_1=5+3=8 $$

---

Now, I am not sure that this is correct, thus, I will be glad for some help. I think that might be better to convert this problem to another problem, but I think that this is good too. Thanks!

Answer 1

A tree $t$ is valid if and only if the subtrees $t_1, t_2, t_3, \ldots$ represented in the figure below are valid and contain an even number of internal nodes

$\qquad$

Let $T_n$ be the set all of valid trees with $n$ internal nodes and let $T_{n,k}$ be the set of trees from $T_n$ with $k$ internal nodes on their rightmost branch. Then $T_n$ is the disjoint union of the $T_{n,k}$ for $1 \leqslant k \leqslant n$. Moreover, a tree of $T_{n,k}$ can be constructed, as explained in the figure, from valid trees $t_1, \ldots, t_k$ each of them having an even number of internal nodes. It follows that $$ D_n = |T_n| = \sum_{1 \leqslant k \leqslant n} |T_{n,k}| \quad\text{and}\quad |T_{n,k}| = \sum |T_{n_1}| |T_{n_2}| \cdots |T_{n_k}| $$ where the second sum runs over all sequences of even numbers $n_1, \ldots, n_k$ such that $n_1 + \dotsm + n_k + k = n$.

Let us compute the first values, starting from $D_1 = 1$ and $D_2 = 1$. The set $T_2$ only contains the tree

$\qquad$

and $T_3$ contains the two trees

$\qquad$

Next $T_4$ contains the three trees

$\qquad$

and $T_5$ contains the seven trees

Thus $D_1 = 1$, $D_2 = 1$, $D_3 = 2$, $D_4 = 3$ and $D_5 = 7$, which already shows that the conjectured formula $D_n = D_{n-1} + D_{n-2}$ is wrong. Computation gives $D_6 = 12$, $D_7 = 30$, $D_8 = 55$, $D_9 = 143$, $\ldots$, which matches the A047749 OEIS sequence. Thus it seems that $$ D_n = \begin{cases} \frac{1}{2m+1} \binom{3m}{m}&\text{if $n = 2m$}\\ \frac{1}{2m+1} \binom{3m+1}{m+1}&\text{if $n = 2m+1$} \end{cases} $$ but this formula remains to be proved.

Answer 2

this answer is not correct as J-E-pin pointed out

my take on this question:

it's pretty easy to see that $D_1 = 1$ and $D_2 = 1$.
we use these two as our bases. we can create a valid tree with n internal vertex in one of two methods:

1. take a tree with n-1 internal vertexes and replace its rightmost node with $D_1$, this way we get an n-sized tree while maintaining the required properties, adding $D_1$ to any other node will create an invalid tree.

2. take a tree with n-2 internal vertexes and replace its leftmost node with $D_2$, this way we get an n-sized tree while maintaining the required properties, adding $D_2$ to any other node will create an invalid tree.

so we got: $D_n = D_{n-1} + D_{n-2}$