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
|
#+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.
|
