combinatorial mathematics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...

, Catalan's triangle is a number triangle whose entries

C(n,k)

give the number of strings consisting of ''n'' X's and ''k'' Y's such that no initial segment of the string has more Y's than X's. It is a generalization of the

Catalan numbers In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Cata ...

, and is named after

Eugène Charles Catalan Eugène Charles Catalan (30 May 1814 – 14 February 1894) was a French and Belgian mathematician who worked on continued fractions, descriptive geometry, number theory and combinatorics. His notable contributions included discovering a periodic ...

. Bailey shows that

C(n,k)

satisfy the following properties: #

C(n,0)=1 \text n\geq 0

. #

C(n,1)=n \text n\geq 1

. #

C(n+1,k)=C(n+1,k-1)+C(n,k) \text 1 # C(n+1,n+1)=C(n+1,n) \text n\geq 1 .
Formula 3 shows that the entry in the triangle is obtained recursively by adding numbers to the left and above in the triangle. The earliest appearance of the Catalan triangle along with the recursion formula is in page 214 of the treatise on Calculus published in 1800 by

Louis François Antoine Arbogast Louis François Antoine Arbogast (4 October 1759 – 8 April 1803) was a French mathematician. He was born at Mutzig in Alsace and died at Strasbourg, where he was professor. He wrote on series and the derivatives known by his name: he was the f ...

. Shapiro introduces another triangle which he calls the Catalan triangle that is distinct from the triangle being discussed here.

General formula

The general formula for

C(n,k)

is given by :

C(n,k)= \binom - \binom

So :

C(n,k) = \frac\binom

When

k=n

, the diagonal is the -th

Catalan number In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Cata ...

. The row sum of the -th row is the -th

, using the

hockey-stick identity In combinatorial mathematics, the identity : \sum^n_= \qquad \text n,r\in\mathbb, \quad n\geq r or equivalently, the mirror-image by the substitution j\to i-r: : \sum^_=\sum^_= \qquad \text n,r\in\mathbb, \quad n\geq r is known as the hockey ...

and an alternative expression for Catalan numbers. Some values are given by : A combinatorial interpretation of the

(n,k-1)

-th value is the number of non-decreasing partitions with exactly parts with maximum part such that each part is less than or equal to its index. So, for example,

(4,2) = 9

counts :

1111, 1112, 1113, 1122, 1123, 1133, 1222, 1223, 1233

Generalization

Catalan's trapezoids are a countable set of number trapezoids which generalize Catalan’s triangle. Catalan's trapezoid of order is a number trapezoid whose entries

C_(n,k)

give the number of strings consisting of X-s and Y-s such that in every initial segment of the string the number of Y-s does not exceed the number of X-s by or more. By definition, Catalan's trapezoid of order is Catalan's triangle, i.e.,

C_(n,k)=C(n,k)

. Some values of Catalan's trapezoid of order are given by : Some values of Catalan's trapezoid of order are given by : Again, each element is the sum of the one above and the one to the left. A general formula for

C_(n,k)

is given by :

C_(n,k)=\begin
\left(\begin
n+k\\
k
\end\right) & \,\,\,0\leq k n+m-1
\end

( , , ).

Proofs of the general formula for $C_(n,k)$

Proof 1

This proof involves an extension of the Andres Reflection method as used in the second proof for the

to different diagonals. The following shows how every path from the bottom left

(0,0)

to the top right

(k, n)

of the diagram that crosses the constraint

n-k+m-1 = 0

can also be reflected to the end point

(n + m, k - m)

We consider three cases to determine the number of paths from

(0,0)

(k, n)

that do not cross the constraint: (1) when

m > k

the constraint cannot be crossed, so all paths from

(0,0)

(k, n)

are valid, i.e.

C_(n,k)=\left(\begin
n+k\\
k
\end\right)

. (2) when

k - m + 1 > n

it is impossible to form a path that does not cross the constraint, i.e.

C_(n,k)= 0

. (3) when

m\leq k\leq n+m-1

, then

C_(n,k)

is the number of 'red' paths

\left(\begin
n+k\\
k
\end\right)

minus the number of 'yellow' paths that cross the constraint, i.e.

\left(\begin
(n+m)+(k-m)\\
k-m
\end\right) = \left(\begin
n+k\\
k-m
\end\right)

. Therefore the number of paths from

(0,0)

(k, n)

that do not cross the constraint

n - k + m - 1 = 0

is as indicated in the formula in the previous section "''Generalization''".

Proof 2

Firstly, we confirm the validity of the recurrence relation

C_(n,k)=C_(n-1,k)+C_(n,k-1)

by breaking down

C_(n,k)

into two parts, the first for XY combinations ending in X and the second for those ending in Y. The first group therefore has

C_(n-1,k)

valid combinations and the second has

C_(n,k-1)

. Proof 2 is completed by verifying the solution satisfies the recurrence relation and obeys initial conditions for

C_(n,0)

and

C_(0,k)

References