Sum-difference sequences and Catalan numbers (Q1291092): Difference between revisions

The sequence \(a_0=1\), \(a_1,a_2,\dots,a_n\), \(a_{n+1}=1\) of natural numbers is called admissible if \(a_1\) divides \(a_{i-1}+a_{i+1}\) for all \(i=1,2,\dots,n\). The number of such sequences is equal to the Catalan number \(C_n\). Various proofs of this are known; in the present paper it is proved by establishing a bijection between the sequences and a set of rooted binary trees. This correspondence is also used to count sequences with a given number of local maxima, or a given number of rises, etc. The Narayama numbers, Motzkin numbers and ballot numbers appear in the results. Number-theoretic properties are also investigated and here the Fibonacci numbers occur.