Catalan interpretation

Question

I have question and I think the answer is equal with Catalan numbers. The question as follows:

The number of the sequence $a_0a_1a_2\cdots a_na_{n+1}$ of integers with $a_i\geq 2, a_0=a_{n+1}=1$ and $a_i \vert (a_{i-1}+a_{i+1})$, where $1\leq i\leq n$ is equal Catalan numbers.

I obtained some values of these sequences:

For $n=1$ we have $121$,

For $n=2$, we have $1231, 1321$,

For $n=3$, we have $12341, 12531, 13231, 13521, 14321$

For $n=4$, we have $$123451,123741,125341,125831,127531,132341,132531,135231,135721,138521,143231,143521,147321,154321.$$

I try to define bijection between these sequence and other interoperation of Catalan numbers.

Please let me know if you have any comments to help. Thanks.

Answer 1

Note that every valid sequence has three consecutive entries $a,c,b$ for which $c=a+b$. Indeed, you can let $c$ be any maximal element of the sequence. Furthermore, when you delete this $c$ from the sequence, the remaining sequence is still valid. Conversely, you can extend any valid sequence by taking two adjacent terms, $a$ and $b$, and inserting $a+b$ between them. The key observation is that every sequence can be built starting from $11$, and repeatedly performing these insertions. It turns out that all of the ways to perform the insertions are exactly described by binary trees.

Here is a bijection between valid sequences and binary trees with $n+1$ leaves. I will illustrate via example with the sequence $132531$. Start with $n+1$ unconnected vertices, which will be the leaves of the tree. The vertices are labeled with the pairs of consecutive entries in the list. Since the list has $n+2$ numbers, there are $n+1$ consecutive pairs.

13  32  25  53  31

Then, we join up certain pairs of these vertices which are adjacent in left-to-right order, as follows. If $ac$ and $cb$ are adjacent, then they are joined together if and only if $c=a+b$ (we showed earlier that such a pair always exists). The two are joined to a parent node, which is labeled $ab$.

  12      23
 /  \    /  \
13  32  25  53  31

You then repeat this process, constraining your attention to the set of nodes which do not have parents. So, in the above diagram, we look at $[12,23,31]$, and see that only $23$ and $31$ can be joined together (because $3=2+1$) to a node labeled $21$. This leaves the parent nodes $12$ and $21$, which can be joined to $11$. This is the completed tree:

        11
       /  \
      /    \
     /      21
    /      /  \
  12      23   \
 /  \    /  \   \
13  32  25  53  31

This mapping from valid sequences to binary trees is a bijection because it has an inverse mapping. Given a binary tree, label the root with $11$, and then for each internal node labeled $ab$, label its left child with $a(a+b)$ and its right child with $(a+b)b$. The sequence of leaves, read left to right, will be of the form $1a_1,a_1a_2,\dots,a_n1$, and the inverse operation outputs $1a_1a_2\dots a_n1$. Since $11$ is valid, and the insertion operation preserves validity, the resulting sequence is valid.