Catalan's triangle

Last updated

In combinatorial mathematics, Catalan's triangle is a number triangle whose entries 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, and is named after Eugène Charles Catalan. Bailey [1] shows that satisfy the following properties:

Contents

  1. .
  2. .
  3. .

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 [2] by Louis François Antoine Arbogast.

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

General formula

The general formula for is given by [1] [4]

So

When , the diagonal C(n, n) is the n-th Catalan number.

The row sum of the n-th row is the (n + 1)-th Catalan number, using the hockey-stick identity and an alternative expression for Catalan numbers.

Table of values

Some values are given by [5]

 k
n 
012345678
01
111
2122
31355
41491414
51514284242
616204890132132
7172775165297429429
81835110275572100114301430

Properties

That is, an entry is the partial sum of the above row and also the partial sum of the column to the left (except for the entry on the diagonal).

Generalization

Catalan's trapezoids are a countable set of number trapezoids which generalize Catalan’s triangle. Catalan's trapezoid of order m = 1, 2, 3, ... is a number trapezoid whose entries give the number of strings consisting of n X-s and k 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 m or more. [6] By definition, Catalan's trapezoid of order m = 1 is Catalan's triangle, i.e., .

Some values of Catalan's trapezoid of order m = 2 are given by

 k
n 
012345678
011
1122
21355
31491414
41514284242
516204890132132
6172775165297429429
71835110275572100114301430

Some values of Catalan's trapezoid of order m = 3 are given by

 k
n 
0123456789
0111
11233
213699
31410192828
4151534629090
5162155117207297297
617288320040770410011001
718361193197261430243134323432

Again, each element is the sum of the one above and the one to the left.

A general formula for is given by

( n = 0, 1, 2, ..., k = 0, 1, 2, ..., m = 1, 2, 3, ...).

Proofs of the general formula

Proof 1

This proof involves an extension of Andre's reflection method as used in the second proof for the Catalan number to different diagonals. The following shows how every path from the bottom left to the top right of the diagram that crosses the constraint can also be reflected to the end point .

General catalan number proof.png

We consider three cases to determine the number of paths from to that do not cross the constraint:

(1) when the constraint cannot be crossed, so all paths from to are valid, i.e. .

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

(3) when , then is the number of 'red' paths minus the number of 'yellow' paths that cross the constraint, i.e. .

Therefore the number of paths from to that do not cross the constraint is as indicated in the formula in the previous section "Generalization".

Proof 2

Firstly, we confirm the validity of the recurrence relation by breaking down into two parts, the first for XY combinations ending in X and the second for those ending in Y. The first group therefore has valid combinations and the second has . Proof 2 is completed by verifying the solution satisfies the recurrence relation and obeys initial conditions for and .

References

  1. 1 2 Bailey, D. F. (1996). "Counting Arrangements of 1's and -1's". Mathematics Magazine. 69 (2): 128–131. doi:10.1080/0025570X.1996.11996408.
  2. Arbogast, L. F. A. (1800). Du Calcul des Derivations. Levrault. p.  214.
  3. Shapiro, L. W. (1976). "A Catalan Triangle". Discrete Mathematics. 14 (1): 83–90. doi: 10.1016/0012-365x(76)90009-1 .
  4. Eric W. Weisstein. "Catalan's Triangle". MathWorld − A Wolfram Web Resource. Retrieved March 28, 2012.
  5. Sloane, N. J. A. (ed.). "SequenceA009766(Catalan's triangle)". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation. Retrieved March 28, 2012.
  6. Reuveni, Shlomi (2014). "Catalan's trapezoids". Probability in the Engineering and Informational Sciences. 28 (3): 4391–4396. doi:10.1017/S0269964814000047. S2CID   122765015.