Reference for a definition of Catalan numbers

Question

The $l$-th Catalan number ${2l\choose l}\frac{1}{l+1}$ is equal to the number of sequences $s_0,\ldots,s_{l+1}$ of length $l+2$ with the following properties:

(1) $s_0=s_{l+1}=1$ and $s_1,\ldots,s_l$ are integers $\geq 2$,

(2) $s_i$ divides $s_{i-1}+s_i+s_{i+1}$ for $i=1,\ldots,l$.

(The proof is easy: consecutive terms $s_is_{i+1}$ in such sequences encode leaves of finite binary trees with $l+1$ leaves. This encoding of binary trees has nice properties: the integer $(s_{i-1}+s_i+s_{i+1})/s_i$ is the distance between the consecutive leaves encoded by $s_{i-1},s_i$ and $s_i,s_{i+1}$. Leaves correspond always to coprime integers $s_i,s_{i+1}$ and heights of leaves can be computed by applying Euclid's algorithm (essentially by summing all quotients occuring during the computation) to the coprime pair $(s_i,s_{i+1})$. Interior vertices of the binary tree encoded by $s_0,\ldots,s_{l+1}$ correspond to segments $s_i,s_{i+1},\ldots,s_{i+k}$ such that $s_{i+1},\ldots,s_{i+k-1}$ are all strictly larger than $\max(s_i,s_{i+k})$ (and the height of such an interior vertex is given as for leaves by Euclid's algorithm applied to $s_i,s_{i+k}$ which are always coprime). In particular the binary tree of the left child of the root vertex (for $l\geq 1$) is encoded by the initial terms $s_0,\ldots,s_i=2$. The subtree for the right child corresponds to $s_i=2,\ldots,s_{l+1}$.)

Examples (with integers concatenated):

$l=0$: $11$,

$l=1$: $121$,

$l=2$: $1231,1321$,

$l=3$: $12341,12531,13231,13521,14321$.

(Recipe for recursive constructions: All such sequences of length $l+3$ are obtained from such sequences $l+2$ by inserting in all possible ways between two adjacent terms their sum.)

Is there a reference for this description? (I could not find it in Stanley's list but a mistake on my behalf is likely.)

Answer 1

I'm converting my comments to an answer. This interpretation of the Catalan numbers is indeed well-known. It appears for instance as Exercise 92 in Chapter 2 of Stanley's book on Catalan numbers, as well as Exercise 6.19(iii) in his Enumerative Combinatorics, Vol. 2. It is also discussed, for instance, in the paper Sum-Difference Sequences and Catalan Numbers by Aigner & Schulze, who attribute this interpretation to Van Lint.

(By the way, it is a little unclear why you write "$s_i$ divides $s_{i-1}+s_i+s_{i+1}$" instead of "$s_i$ divides $s_{i-1}+s_{i+1}$", but of course that amounts to the same thing.)