1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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.
|
