Catalan's triangle
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 shows that  satisfy the following properties:
 .
 .

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

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  is given by

So

When , the diagonal  is the -th Catalan number.

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

Table of values

Some values are given by 
{| class="wikitable" style="text-align:right;"
|-
! 
! width="50" | 0
! width="50" | 1
! width="50" | 2
! width="50" | 3
! width="50" | 4
! width="50" | 5
! width="50" | 6
! width="50" | 7
! width="50" | 8
|-
! 0
| 1 || || || || || || || ||
|-
! 1
| 1 || 1 || || || || || || ||
|-
! 2
| 1 || 2 || 2 || || || || || ||
|-
! 3
| 1 || 3 || 5 || 5 || || || || ||
|-
! 4
| 1 || 4 || 9 || 14 || 14 || || || ||
|-
! 5
| 1 || 5 || 14 || 28 || 42 || 42 || || ||
|-
! 6
| 1 || 6 || 20 || 48 || 90 || 132 || 132 || ||
|-
! 7
| 1 || 7 || 27 || 75 || 165 || 297 || 429 || 429 ||
|-
! 8
| 1 || 8 || 35 || 110 || 275 || 572 || 1001 || 1430 || 1430
|}

Properties

 Formula 3 from the first section can be used to prove both

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).

 If , then at some stage there must be more 's than 's, so .

 A combinatorial interpretation of the -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,  counts

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  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., .

Some values of Catalan's trapezoid of order   are given by 
{| class="wikitable" style="text-align:right;"
|-
! 
! width="50" | 0
! width="50" | 1
! width="50" | 2
! width="50" | 3
! width="50" | 4
! width="50" | 5
! width="50" | 6
! width="50" | 7
! width="50" | 8
|-
! 0
| 1 || 1 || || || || || || || 
|-
! 1
| 1 || 2 || 2 || || || || || || 
|-
! 2
| 1 || 3 || 5 || 5 || || || || || 
|-
! 3
| 1 || 4 || 9 || 14 || 14 || || || ||
|-
! 4
| 1 || 5 || 14 || 28 || 42 || 42 || || ||
|-
! 5
| 1 || 6 || 20 || 48 || 90 || 132 || 132 || ||
|-
! 6
| 1 || 7 || 27 || 75 || 165 || 297 || 429 || 429 || 
|-
! 7
| 1 || 8 || 35 || 110 || 275 || 572 || 1001 || 1430 || 1430  
|}

Some values of Catalan's trapezoid of order   are given by 
{| class="wikitable" style="text-align:right;"
|-
! 
! width="50" | 0
! width="50" | 1
! width="50" | 2
! width="50" | 3
! width="50" | 4
! width="50" | 5
! width="50" | 6
! width="50" | 7
! width="50" | 8
! width="50" | 9
|-
! 0
| 1 || 1 || 1 || || || || || || || 
|-
! 1
| 1 || 2 || 3 || 3 || || || || || || 
|-
! 2
| 1 || 3 || 6 || 9 || 9 || || || || || 
|-
! 3
| 1 || 4 || 10 || 19 || 28 || 28 || || || || 
|-
! 4
| 1 || 5 || 15 || 34 || 62 || 90 || 90 || || || 
|-
! 5
| 1 || 6 || 21 || 55 || 117 || 207 || 297 || 297 || || 
|-
! 6
| 1 || 7 || 28 || 83 || 200 || 407 || 704 || 1001 || 1001 || 
|-
! 7
| 1 || 8 || 36 || 119 || 319 || 726 || 1430 || 2431 || 3432 || 3432  
|}
Again, each element is the sum of the one above and the one to the left.

A general formula for  is given by

( ,   ,   ).

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 . 

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

Triangles of numbers