diff options
Diffstat (limited to 'posts/2015-01-20-weighted-interpretation-super-catalan-numbers.md')
| -rw-r--r-- | posts/2015-01-20-weighted-interpretation-super-catalan-numbers.md | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/posts/2015-01-20-weighted-interpretation-super-catalan-numbers.md b/posts/2015-01-20-weighted-interpretation-super-catalan-numbers.md new file mode 100644 index 0000000..6d9e75e --- /dev/null +++ b/posts/2015-01-20-weighted-interpretation-super-catalan-numbers.md @@ -0,0 +1,40 @@ +--- +template: oldpost +title: AMS review of 'A weighted interpretation for the super Catalan numbers' by Allen and Gheorghiciuc +date: 2015-01-20 +comments: true +archive: false +--- +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; +[MR1187230](http://www.ams.org/mathscinet/search/publdoc.html?r=1&pg1=MR&s1=1187230&loc=fromrevtext)\]: +\$\$ 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](http://www.ams.org/mathscinet/search/publdoc.html?r=1&pg1=MR&s1=2134162&loc=fromrevtext)\], +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. |