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 :
- A single vertex.
- 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!
Best Answer
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.