A Generalization of the Catalan Numbers

Reza Kahkeshani Department of Pure Mathematics Faculty of Mathematical Sciences University of Kashan Kashan Iran

                 kahkeshanireza@kashanu.ac.ir

Abstract In this paper, we generalize the Catalan number C_{n} to the (m, n)th Catalan number C(m, n) using a combinatorial description, as follows: the number of paths in ℝ^{m} from the origin to the point (\underbrace{n, …, n}_{m−1}, (m − 1)n) with m kinds of moves such that the path

never rises above the hyperplane x_{m} = x_{1} + ⋯ + x_{m−1}.

1 Introduction

Catalan numbers (\underline{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 by n − 1 diagonals that do not intersect in their interiors.

• Binary parenthesizations of a string of n + 1 letters.

• Binary trees with n vertices.

The solution to these problems is the nth Catalan number

C_{n} = \frac{1}{n + 1}\binom{2n}{n},

and the sequence C_{0}, C_{1}, C_{2}, …, C_{n}, … 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 or k-Catalan numbers, defined by

C_{n}^{k} = \frac{1}{kn + 1}\binom{kn + 1}{n} = \frac{1}{(k − 1)n + 1}\binom{kn}{n} = \frac{1}{n}\binom{kn}{n − 1},

where k, n ∈ ℕ. Clearly, C_{n}^{2} = C_{n}. 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 by k-ary numbers [5, 6, 8, 10]. Moreover, Kim [7, Thm. 2] showed that C_{n}^{k} 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 the k-Catalan numbers as special cases, defined as

A_{n}(a, b) = \frac{a}{a + bn}\binom{a + bn}{n},

and showed the following convolution formula for these sequences:

∑_{k=0}^{n} A_{k}(a, b)A_{n−k}(c, b) = A_{n}(a + c, b).

These numbers are also known as the Rothe numbers [9] and Rothe-Hagen coefficients of the first type [4]. Clearly, A_{n}(1, 2) = C_{n} and A_{n}(1, k) = C_{n}^{k}.

We know that one of the interpretations of the Catalan numbers is the movements in ℝ^{2} with two kinds of moves such that the path never rises above the line y = x. In this paper, a new generalization of the Catalan numbers using this interpretation is introduced. Consider m kinds of moves in ℝ^{m} such that they are one unit parallel to the positive axes. We show that the number of paths from the origin to the point (\underbrace{n, …, n}_{m−1}, (m−1)n) using these moves

such that the path never rises above the hyperplane x_{m} = x_{1} + ⋯ + x_{m−1} is

\frac{1}{n(m − 1) + 1}\binom{2n(m − 1)}{\underbrace{n, …, n}_{m−1}, n(m − 1)}.

We call this number the (m, n)th Catalan number C(m, n). Clearly, C(2, n) is the ordinary nth Catalan number C_{n}.

2 Generalization

In this section, we prove the our main theorem. We show that the generalized Catalan numbers C(m, n) are given by

\frac{1}{n(m − 1) + 1}\binom{2n(m − 1)}{\underbrace{n, …, n}_{m−1}, n(m − 1)}.

Theorem 1. Let ℝ^{m} be the m-dimensional vector space. Consider

R_{1} : (x_{1}, x_{2}, …, x_{m}) ⟶ (x_{1} + 1, x_{2}, …, x_{m}),
R_{2} : (x_{1}, x_{2}, …, x_{m}) ⟶ (x_{1}, x_{2} + 1, …, x_{m}),
⋮
R_{m} : (x_{1}, x_{2}, …, x_{m}) ⟶ (x_{1}, x_{2}, …, x_{m} + 1),

be m kinds of moves in ℝ^{m} (i.e., R_{i} denotes the move one unit parallel to the x_{i}-axis in the positive direction). Then the number of paths from 0 = (\underbrace{0, …, 0}_{m}) to the point N :=

(\underbrace{n, …, n}_{m−1}, (m − 1)n) using the moves R_{1}, R_{2}, …, R_{m} such that the path never rises above the

hyperplane x_{m} = x_{1} + ⋯ + x_{m−1} is

\frac{1}{n(m − 1) + 1}\binom{2n(m − 1)}{\underbrace{n, …, n}_{m−1}, n(m − 1)}.

Proof. We call a path from 0 to N of n R_{1}’s, n R_{2}’s, …, n R_{m−1}’s, and (m − 1)n R_{m}’s acceptable if the path never rises above the hyperplane x_{m} = x_{1} + ⋯ + x_{m−1} and unacceptable otherwise. Let A_{n}^{m} and U_{n}^{m} denote the number of acceptable and unacceptable paths, respectively. It is easy to see that each path from 0 to N corresponds to an arrangement of n R_{1}’s, n R_{2}’s, …, n R_{m−1}’s, and (m − 1)n R_{m}’s. Then

A_{n}^{m} + U_{n}^{m} = \frac{(2n(m − 1))!}{n!^{m−1}(n(m − 1))!}.

Now, consider an unacceptable path and its arrangement r_{1}, r_{2}, …, r_{2n(m−1)}, where r_{i} ∈ {R_{1}, R_{2}, …, R_{m}} indicates the ith step of the path. Since the path rises above the hyperplane, there is a first t such that the number of R_{m}’s in r_{1}, …, r_{t} exceeds the sum of the numbers R_{1}, R_{2}, …, R_{m−1}. Moreover, r_{t} = R_{m}. We only change r_{t+1}, …, r_{2n(m−1)} the part of the path after the crossing in the arrangement as follows: Mark all the positions of the R_{m}’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-R_{m}’s. Then replace those non-R_{m}’s that have been used in the replacement with R_{m}’s. Here is an example: let m = 3, n = 2 and the path be given by R_{1}R_{3}R_{2}R_{3}R_{3}R_{1}R_{2}R_{3}. Then t = 5, and the part of the path to be modified is R_{1}R_{2}R_{3}. There is just one position of the R_{m}’s, so we replace R_{3} with R_{1}, and then fill the R_{1}R_{2} with R_{3}R_{3} to obtain the modified sequence R_{1}R_{3}R_{2}R_{3}R_{3}R_{3}R_{3}R_{1}. The resulting arrangement

r1^{′}, r2^{′}, …, r2n(m−1)^{′} is an arrangement of (m − 1)n + 1 R_{m}’s, n R_{1}’s, …, n R_{i−1}’s, n R_{i+1}’s,

…, n R_{m−1}’s, and n − 1 R_{i}’s for a 1 ≤ i ≤ m − 1. It is not difficult to see that this process is reversible:

r_{1}, r_{2}, …, r_{2n(m−1)}
⇕

\underbrace{∗, ∗, …, ∗, R_{m}}_{\begin{matrix}rR_{m}’s, \\ r−1R_{1},...,R_{m−1}’s. \end{matrix}} | \underbrace{∗, ∗, …, ∗}_{\begin{matrix}(m−1)n−rR_{m}’s, \\ (m−1)n−r+1R_{1},...,R_{m−1}’s. \end{matrix}}

⇕

\underbrace{∗, ∗, …, ∗, R_{m}}_{\begin{matrix}rR_{m}’s, \\ r−1R_{1},...,R_{m−1}’s. \end{matrix}} | \underbrace{∗, ∗, …, ∗}_{\begin{matrix}(m−1)n−r+1R_{m}’s, \\ (m−1)n−rR_{1},...,R_{m−1}’s. \end{matrix}}

⇕

r1^{′}, r2^{′}, …, r2n(m−1)^{′}

Hence, there are as many unacceptable arrangements as there are arrangements of (m−1)n+1 R_{m}’s, n R_{1}’s, …, n R_{i−1}’s, n R_{i+1}’s, …, n R_{m−1}’s, and n − 1 R_{i}’s for a 1 ≤ i ≤ m − 1. Then

U_{n}^{m} = (m − 1)\frac{(2n(m − 1))!}{n!^{m−2}(n − 1)!(n(m − 1) + 1)!}.

So,

A_{n}^{m} =\frac{(2n(m − 1))!}{n!^{m−1}(n(m − 1))!} − (m − 1)\frac{(2n(m − 1))!}{n!^{m−2}(n − 1)!(n(m − 1) + 1)!}
=\frac{(2n(m − 1))!}{n!^{m−2}(n − 1)!(n(m − 1))!}(\frac{1}{n} − \frac{m − 1}{n(m − 1) + 1})
=\frac{(2n(m − 1))!}{n!^{m−1}(n(m − 1) + 1)!}
=\frac{1}{n(m − 1) + 1}\binom{2n(m − 1)}{\underbrace{n, …, n}_{m−1}, n(m − 1)}.

We denote A_{n}^{m} in the above proof by C(m, n). The first few generalized Catalan numbers are evaluated to be

\begin{matrix}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 \end{matrix}

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, Discrete 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, generalized 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 Virginia, 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 sequence \underline{A000108}.)

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.