# Recursive formula for a tree problem

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!

• @RobPratt can you have your opinion on this question? Jul 20, 2021 at 7:00
• That recurrence would mean $D_n$ are the Fibonacci numbers oeis.org/A000045 . The equivalence to the interpretation of Fibonacci numbers with domino-stacking of 2xn lanes would be that the root nodes are those with a "vertical" domino and the child nodes with 2 "horizontal" dominos. Jul 20, 2021 at 12:37
• @R.J.Mathar I didn't get what you are trying to say. I am sorry. can you elaborate? Jul 20, 2021 at 13:00
• The counting of domino stacks on 2xn lanes is for example illustrated in mathworld.wolfram.com/FibonacciNumber.html, and the equivalence is one of the very well known properties of the Fibonacci numbers, as for example mentioned in the OEIS. The point here is that a stack can be extended from n to n+1 lanes by either addin a vertical domino or 2 horizontal dominoes to get another stack. Jul 22, 2021 at 10:25
• @R.J.Mathar and what it has to do with the question? Jul 22, 2021 at 16:35

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.

• Thank you! it's a great answer! Jul 28, 2021 at 7:51

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

• Unfortunately, $D_5 \not= D_3 + D_4$, so your answer is not correct. Jul 27, 2021 at 21:42
• @J.-E.Pin Thanks, edited Jul 28, 2021 at 23:25