Catalan's triangle

The general formula for C(n,k) is given by :C(n,k)= \binom{n+k}{k} - \binom{n+k}{k-1} So :C(n,k) = \frac{n-k+1}{n+1}\binom{n+k}{k} When k=n, 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 : ==Properties==

• Formula 3 from the first section can be used to prove both :C(n,k) = \sum_{i=0}^k C(n-1,i) = \sum_{i=k}^n C(i,k-1) 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 k>n, then at some stage there must be more 's than 's, so C(n,k)=0. • 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_{m}(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_{1}(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_{m}(n,k) is given by :C_{m}(n,k)=\begin{cases} \left(\begin{array}{c} n+k\\ k \end{array}\right) & \,\,\,0\leq kn+m-1 \end{cases} ( , , ). == 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 (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) to (k, n) that do not cross the constraint: (1) when m > k the constraint cannot be crossed, so all paths from (0,0) to (k, n) are valid, i.e. C_{m}(n,k)=\left(\begin{array}{c} n+k\\ k \end{array}\right). (2) when k - m + 1 > n it is impossible to form a path that does not cross the constraint, i.e. C_{m}(n,k)= 0 . (3) when m\leq k\leq n+m-1 , then C_{m}(n,k) is the number of 'red' paths \left(\begin{array}{c} n+k\\ k \end{array}\right) minus the number of 'yellow' paths that cross the constraint, i.e. \left(\begin{array}{c} (n+m)+(k-m)\\ k-m \end{array}\right) = \left(\begin{array}{c} n+k\\ k-m \end{array}\right). Therefore the number of paths from (0,0) to (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_{m}(n,k)=C_{m}(n-1,k)+C_{m}(n,k-1) by breaking down C_{m}(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_{m}(n-1,k) valid combinations and the second has C_{m}(n,k-1). Proof 2 is completed by verifying the solution satisfies the recurrence relation and obeys initial conditions for C_{m}(n,0) and C_{m}(0,k). ==References==