Transformation of the Catalan Numbers and Related Counted Sets

Abstract

Borel's triangle is a triangular array of numbers constructed by a transformation of the Catalan numbers. By identifying natural bijections between them, we discuss several sets counted by Borel's triangle, including full binary trees with a fixed number of "marked" branching vertices, ballot sequences in elections between three parties, and permutations with a given set of properties. We further introduce a strategy which can be used to identify more combinatorial interpretations of Borel's triangle.