Sum-difference sequences and Catalan numbers

DOI10.1007/S006050050025MaRDI QIDQ1291092zbMATH OpenOpenAlexFDO

Authors Martin Aigner, Volker Schulze

Publication date 3 June 1999

Published in Monatshefte für Mathematik (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s006050050025

zbMATH Keywords

admissible sequencesballot numbersCatalan numberFibonacci numbersMotzkin numbersNarayama numbersrooted binary trees

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Sequences and sets (11B99)

Review text

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.

Recommendations

• Sequences that satisfy a(n-a(n))=0
• Two integer sequences related to Catalan numbers
• Recursive bijections for Catalan objects
• Generalizing Bailey's generalization of the Catalan numbers

Cited in

(4)

• Counting arithmetical structures on paths and cycles
• Enumeration via ballot numbers
• Sequences that satisfy a(n-a(n))=0
• Catalan-like numbers and Stieltjes moment sequences

This page was built for publication: Sum-difference sequences and Catalan numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1291092)