8
$\begingroup$

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:

enter image description here

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!

$\endgroup$
6
  • $\begingroup$ @RobPratt can you have your opinion on this question? $\endgroup$
    – Chopin
    Jul 20, 2021 at 7:00
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 20, 2021 at 12:37
  • $\begingroup$ @R.J.Mathar I didn't get what you are trying to say. I am sorry. can you elaborate? $\endgroup$
    – Chopin
    Jul 20, 2021 at 13:00
  • $\begingroup$ 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. $\endgroup$ Jul 22, 2021 at 10:25
  • $\begingroup$ @R.J.Mathar and what it has to do with the question? $\endgroup$
    – Chopin
    Jul 22, 2021 at 16:35

2 Answers 2

2
+100
$\begingroup$

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

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

and $T_3$ contains the two trees

$\qquad$T_3

Next $T_4$ contains the three trees

$\qquad$ T_4

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.

$\endgroup$
1
  • $\begingroup$ Thank you! it's a great answer! $\endgroup$
    – Chopin
    Jul 28, 2021 at 7:51
1
$\begingroup$

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

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

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.