A combinatorial interpretation of the Catalan transform of the Catalan numbers

2011/11/03 by David Callan, Callan, David
Computer Science · Mathematics · #05A15 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A15 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1111.0996

5 pages, added reference

openalex publication_date 2011/11/03 · arxiv created 2011/11/10 · arxiv updated 2011/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Catalan transform of a sequence (a_n)_n>=0 is the sequence (b_n)_n>=0 with b_n = Sum[k/(2n-k) (2n-k)-choose-(n-k) a_k,k=0..n]. Here we show that the Catalan transform of the Catalan numbers has a simple interpretation: it counts functions f:[1,n] -> [1,n] satisfying the condition that, for all i<j, f(j)-(j-i) is not in the interval [1,f(i)-1].

Related

• Are the Catalan Numbers a Linear Recurrence Sequence?
• Notes on the Hankel transform of linear combinations of consecutive pairs of Catalan numbers
• The Hankel Transform of the Sum of Consecutive Generalized Catalan Numbers
• Catalan Tree & Parity of some sequences which are related to Catalan numbers
• Alternating Convolutions of Catalan Numbers