AMS review of 'A weighted interpretation for the super Catalan numbers' by Allen and Gheorghiciuc

Posted on 2015-01-20

The super Catalan numbers are defined as $$ T(m,n) = {(2 m)! (2 n)! 2 m! n! (m + n)!}. $$

   This paper has two main results. First a combinatorial interpretation of the super Catalan numbers is given: $$ T(m,n) = P(m,n) - N(m,n) $$ where \(P(m,n)\) enumerates the number of 2-Motzkin paths whose \(m\) -th step begins at an even level (called \(m\)-positive paths) and \(N(m,n)\) those with \(m\)-th step beginning at an odd level (\(m\)-negative paths). The proof uses a recursive argument on the number of \(m\)-positive and -negative paths, based on a recursion of the super Catalan numbers appearing in [I. M. Gessel, J. Symbolic Comput. 14 (1992), no. 2-3, 179–194; MR1187230]: $$ 4T(m,n) = T(m+1, n) + T(m, n+1). $$ This result gives an expression for the super Catalan numbers in terms of numbers counting the so-called ballot paths. The latter sometimes are also referred to as the generalised Catalan numbers forming the entries of the Catalan triangle.

   Based on the first result, the second result is a combinatorial interpretation of the super Catalan numbers \(T(2,n)\) in terms of counting certain Dyck paths. This is equivalent to a theorem, which represents \(T(2,n)\) as counting of certain pairs of Dyck paths, in [I. M. Gessel and G. Xin, J. Integer Seq. 8 (2005), no. 2, Article 05.2.3, 13 pp.; MR2134162], and the equivalence is explained at the end of the paper by a bijection between the Dyck paths and the pairs of Dyck paths. The proof of the theorem itself is also done by constructing two bijections between Dyck paths satisfying certain conditions. All the three bijections are formulated by locating, removing and adding steps.

Copyright notice: This review is published at http://www.ams.org/mathscinet-getitem?mr=3275875, its copyright owned by the AMS.