23 11
Article 13.6.8
Journal of Integer Sequences, Vol. 16 (2013),
2 3 6 1
47
A Generalization of the Catalan Numbers
Reza Kahkeshani
Department of Pure Mathematics Faculty of Mathematical Sciences
University of Kashan Kashan
Iran
[email protected]
Abstract
In this paper, we generalize the Catalan numberCnto the (m, n)th Catalan number C(m, n) using a combinatorial description, as follows: the number of paths inRm from the origin to the point n, . . . , n
| {z }
m−1
,(m−1)n
with mkinds of moves such that the path never rises above the hyperplane xm =x1+· · ·+xm−1.
1 Introduction
Catalan numbers (A000108) are a very prominent sequence of numbers that arises in a wide varity of combinatorial situations [1,2]. Stanley [10] gave a list of 66 different combinatorial descriptions of Catalan numbers and he added to the list some more [11]. Some of the specific instances are
• The number of movements in xy-plane from (0,0) to (n, n) with two kinds of moves R : (x, y)→(x+ 1, y), U : (x, y)→(x, y+ 1),
such that the path never rises above the line y=x.
• Triangulations of a convex (n+ 2)-gon into n triangles byn−1 diagonals that do not intersect in their interiors.
• Binary parenthesizations of a string ofn+ 1 letters.
• Binary trees with n vertices.
The solution to these problems is the nth Catalan number Cn= 1
n+ 1 2n
n
,
and the sequence C0, C1, C2, . . . , Cn, . . . is called the Catalan sequence.
There have been many attempts to generalize the Catalan numbers. Probably the most important generalization consists of the k-ary numbers ork-Catalan numbers, defined by
Cnk = 1 kn+ 1
kn+ 1 n
= 1
(k−1)n+ 1 kn
n
= 1 n
kn n−1
,
where k, n ∈N. Clearly, Cn2 =Cn. The k-good paths (below the line y =kx) from (0,−1) to n,(k−1)n−1
, staircase tilings and k-ary trees are structures known to be enumerated byk-ary numbers [5, 6, 8,10]. Moreover, Kim [7, Thm. 2] showed that Cnk is the number of partitions of n(k−1) + 2 polygon by (k+ 1)-gon where all vertices of all (k+ 1)-gon lie on the vertices of n(k−1) + 2 polygon. Gould [3] developed a generalization that has both the Catalan numbers and thek-Catalan numbers as special cases, defined as
An(a, b) = a a+bn
a+bn n
, and showed the following convolution formula for these sequences:
Xn
k=0
Ak(a, b)An−k(c, b) =An(a+c, b).
These numbers are also known as the Rothe numbers [9] and Rothe-Hagen coefficients of the first type [4]. Clearly, An(1,2) =Cn and An(1, k) = Cnk.
We know that one of the interpretations of the Catalan numbers is the movements in R2 with two kinds of moves such that the path never rises above the liney =x. In this paper, a new generalization of the Catalan numbers using this interpretation is introduced. Consider m kinds of moves in Rm such that they are one unit parallel to the positive axes. We show that the number of paths from the origin to the point n, . . . , n
| {z }
m−1
,(m−1)n
using these moves such that the path never rises above the hyperplane xm =x1 +· · ·+xm−1 is
1 n(m−1) + 1
2n(m−1) n, . . . , n
| {z }
m−1
, n(m−1)
.
We call this number the (m, n)th Catalan numberC(m, n). Clearly, C(2, n) is the ordinary nth Catalan number Cn.
2 Generalization
In this section, we prove the our main theorem. We show that the generalized Catalan numbers C(m, n) are given by
1 n(m−1) + 1
2n(m−1) n, . . . , n
| {z }
m−1
, n(m−1)
.
Theorem 1. Let Rm be the m-dimensional vector space. Consider R1 : (x1, x2, . . . , xm)−→(x1+ 1, x2, . . . , xm), R2 : (x1, x2, . . . , xm)−→(x1, x2+ 1, . . . , xm),
...
Rm : (x1, x2, . . . , xm)−→(x1, x2, . . . , xm+ 1),
be m kinds of moves in Rm (i.e., Ri denotes the move one unit parallel to the xi-axis in the positive direction). Then the number of paths from 0 = (0, . . . ,0
| {z }
m
) to the point N :=
n, . . . , n
| {z }
m−1
,(m−1)n
using the movesR1, R2, . . . , Rm such that the path never rises above the hyperplane xm =x1+· · ·+xm−1 is
1 n(m−1) + 1
2n(m−1) n, . . . , n
| {z }
m−1
, n(m−1)
.
Proof. We call a path from 0 to N of n R1’s, n R2’s, . . ., n Rm−1’s, and (m−1)n Rm’s acceptable if the path never rises above the hyperplanexm =x1+· · ·+xm−1 and unaccept- able otherwise. Let Amn and Unm denote the number of acceptable and unacceptable paths, respectively. It is easy to see that each path from0 toN corresponds to an arrangement of n R1’s,n R2’s,. . ., n Rm−1’s, and (m−1)n Rm’s. Then
Amn +Unm= 2n(m−1)
! n!m−1 n(m−1)
!.
Now, consider an unacceptable path and its arrangement r1, r2, . . . , r2n(m−1), where ri ∈ {R1, R2, . . . , Rm} indicates the ith step of the path. Since the path rises above the hyper- plane, there is a first t such that the number of Rm’s in r1, . . . , rt exceeds the sum of the numbers R1, R2, . . . , Rm−1. Moreover, rt =Rm. We only change rt+1, . . . , r2n(m−1) the part of the path after the crossing in the arrangement as follows: Mark all the positions of the Rm’s in that part of the path and fill those positions with the sequence (in order) consisting of all but the last of the non-Rm’s. Then replace those non-Rm’s that have been used in
the replacement with Rm’s. Here is an example: let m = 3, n = 2 and the path be given by R1R3R2R3R3R1R2R3. Then t = 5, and the part of the path to be modified is R1R2R3. There is just one position of theRm’s, so we replaceR3 withR1, and then fill theR1R2 with R3R3 to obtain the modified sequence R1R3R2R3R3R3R3R1. The resulting arrangement r′1, r′2, . . . , r′2n(m−1) is an arrangement of (m−1)n+ 1 Rm’s, n R1’s, . . ., n Ri−1’s, n Ri+1’s, . . ., n Rm−1’s, and n−1 Ri’s for a 1≤i≤m−1. It is not difficult to see that this process is reversible:
r1, r2, . . . , r2n(m−1) m
∗,∗, . . . ,∗, Rm
| {z }
rRm’s, r−1R1,...,Rm−1’s.
| ∗,∗, . . . ,∗
| {z }
(m−1)n−rRm’s, (m−1)n−r+1R1,...,Rm−1’s.
m
∗,∗, . . . ,∗, Rm
| {z }
rRm’s, r−1R1,...,Rm−1’s.
| ∗,∗, . . . ,∗
| {z }
(m−1)n−r+1Rm’s, (m−1)n−rR1,...,Rm−1’s.
m
r1′, r′2, . . . , r2n(m−1)′
Hence, there are as many unacceptable arrangements as there are arrangements of (m−1)n+1 Rm’s,n R1’s,. . .,n Ri−1’s,n Ri+1’s,. . ., n Rm−1’s, andn−1Ri’s for a 1≤i≤m−1. Then
Unm = (m−1) 2n(m−1)
!
n!m−2(n−1)! n(m−1) + 1
!. So,
Amn = 2n(m−1)
! n!m−1 n(m−1)
! −(m−1) 2n(m−1)
!
n!m−2(n−1)! n(m−1) + 1
!
= 2n(m−1)
! n!m−2(n−1)! n(m−1)
! 1
n − m−1
n(m−1) + 1
= 2n(m−1)
! n!m−1 n(m−1) + 1
!
= 1
n(m−1) + 1
2n(m−1) n, . . . , n
| {z }
m−1
, n(m−1)
.
We denoteAmn in the above proof byC(m, n). The first few generalized Catalan numbers are evaluated to be
n\m 3 4 5
0 1 1 1
1 4 30 336
2 84 11880 3603600
3 2640 8168160 76881235200
4 100100 7207615800 2229760743210000
5 4232592 7336632122820 77015151194691790080
6 192203088 8193001579963200 2978057806800232994982144 7 9178678080 9763825599821779200 124625746332992720112321024000 8 455053212900 12209602888667136003480 5529032167369807343550830945418000
3 Acknowledgments
The author would like to thank the referee for his/her valuable comments and suggestions which have improved the clarity of the proof of the Theorem 1. This work is partially supported by the University of Kashan under grant number 233437/3.
References
[1] R. A. Brualdi, Introductory Combinatorics, 5th ed., Prentice-Hall, 2009.
[2] R. P. Grimaldi,Discrete and Combinatorial Mathematics, 5th ed., Addison-Wesley, 2004.
[3] H. W. Gould,Combinatorial Identities, Morgantown, West Virginia, 1972.
[4] H. W. Gould, Fundamentals of Series, eight tables based on seven unpublished manuscript notebooks (1945–1990), edited and compiled by J. Quaintance, May 2010.
Available at http://www.math.wvu.edu/~gould/.
[5] S. Heubach, N. Y. Li, and T. Mansour, Staircase tilings and k-Catalan structures, Dis- crete Math. 308 (2008), 5954–5964.
[6] P. Hilton and J. Pedersen, Catalan numbers, their generalization, and their uses, Math.
Intelligencer 13 (2) (1991), 64–75.
[7] D. Kim, On the (n, k)-th Catalan numbers, Commun. Korean Math. Soc. 23 (2008), 349–356.
[8] I. Pak, Reduced decompositions of permutations in terms of star transpositions, gener- alized Catalan numbers and k-ary trees,Discrete Math. 204 (1999), 329–335.
[9] S. L. Richardson, Jr., Enumeration of the generalized Catalan numbers, M.Sc. Thesis, Eberly College of Arts and Sciences, West Virginia University, Morgantown, West Vir- ginia, 2005.
[10] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.
[11] R. P. Stanley, Catalan addendum, preprint, May 25 2013.
Available at http://www-math.mit.edu/~rstan/ec/catadd.pdf.
2000 Mathematics Subject Classification: Primary 05A19; Secondary 05A10, 05A15.
Keywords: Catalan number, path.
(Concerned with sequenceA000108.)
Received March 16 2013; revised version received July 3 2013. Published in Journal of Integer Sequences, July 30 2013.
Return to Journal of Integer Sequences home page.
![2 Higher dimensional Catalan and Narayana numbers, [21], [16], [30]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACH5BAEAAAAALAAAAAABAAEAAAICRAEAOw==)