From 147a19e84a743f1379f05bf2f444143b4afd7bd6 Mon Sep 17 00:00:00 2001 From: Yuchen Pei Date: Fri, 18 Jun 2021 12:58:44 +1000 Subject: Updated. --- ...ighted-interpretation-super-catalan-numbers.org | 39 ++++++++++++++++++++++ 1 file changed, 39 insertions(+) create mode 100644 posts/2015-01-20-weighted-interpretation-super-catalan-numbers.org (limited to 'posts/2015-01-20-weighted-interpretation-super-catalan-numbers.org') diff --git a/posts/2015-01-20-weighted-interpretation-super-catalan-numbers.org b/posts/2015-01-20-weighted-interpretation-super-catalan-numbers.org new file mode 100644 index 0000000..9cde382 --- /dev/null +++ b/posts/2015-01-20-weighted-interpretation-super-catalan-numbers.org @@ -0,0 +1,39 @@ +#+title: AMS review of 'A weighted interpretation for the super Catalan +numbers' by Allen and Gheorghiciuc + +#+date: <2015-01-20> + +The super Catalan numbers are defined as $$ T(m,n) = {(2 m)! (2 n)! +\over 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; +[[http://www.ams.org/mathscinet/search/publdoc.html?r=1&pg1=MR&s1=1187230&loc=fromrevtext][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.; +[[http://www.ams.org/mathscinet/search/publdoc.html?r=1&pg1=MR&s1=2134162&loc=fromrevtext][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. -- cgit v1.2.3