Catalan's triangle

Last updated March 28, 2023

In combinatorial mathematics, 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, and is named after Eugène Charles Catalan. Bailey^[1] shows that $C(n,k)$ 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^[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 $C(n,k)$ is given by^[1]^[4]

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 $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	0	1	2	3	4	5	6	7	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

A combinatorial interpretation of the $(n,k-1)$ -th value is the number of non-decreasing partitions with exactly $n$ parts with maximum part $k$ 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

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

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 $C_{m}(n,k)$ 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., $C_{1}(n,k)=C(n,k)$ .

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

k n	0	1	2	3	4	5	6	7	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 $m = 3$ are given by

k n	0	1	2	3	4	5	6	7	8	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 $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 k<m\\\\\left({\begin{array}{c}n+k\\k\end{array}}\right)-\left({\begin{array}{c}n+k\\k-m\end{array}}\right)&\,\,\,m\leq k\leq n+m-1\\\\0&\,\,\,k>n+m-1\end{cases}}

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

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

Proof 1

This proof involves an extension of the Andres 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)$ .

Related Research Articles

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter. For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a k-combination of a set S is a subset of k distinct elements of S. So, two combinations are identical if and only if each combination has the same members. If the set has n elements, the number of k-combinations, denoted by $or, is equal to the binomial coefficient$

In mathematics, the Euler numbers are a sequence E_n of integers defined by the Taylor series expansion

In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although other mathematicians studied it centuries before him in Persia, India, China, Germany, and Italy.

In mathematics, a generating function is a way of encoding an infinite sequence of numbers by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of 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 Catalan (1814–1894).

In mathematics, the falling factorial is defined as the polynomial

In mathematics, the double factorial of a number $n$ , denoted by $n ‼$ , is the product of all the integers from 1 up to $n$ that have the same parity as $n$ . That is,

In calculus, the trapezoidal rule is a technique for approximating the definite integral.

In probability theory and statistics, the triangular distribution is a continuous probability distribution with lower limit a, upper limit b and mode c, where a < b and a ≤ c ≤ b.

In combinatorics, Vandermonde's identity is the following identity for binomial coefficients:

In calculus, the general Leibniz rule, named after Gottfried Wilhelm Leibniz, generalizes the product rule. It states that if $and are -times differentiable functions, then the product is also -times differentiable and its th derivative is given by$

In mathematics the nth central binomial coefficient is the particular binomial coefficient

In mathematics, particularly in combinatorics, a Stirling number of the second kind is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by $or . Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions.$

In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles.

The Rand index or Rand measure in statistics, and in particular in data clustering, is a measure of the similarity between two data clusterings. A form of the Rand index may be defined that is adjusted for the chance grouping of elements, this is the adjusted Rand index. From a mathematical standpoint, Rand index is related to the accuracy, but is applicable even when class labels are not used.

In mathematics, a Delannoy number $describes the number of paths from the southwest corner (0, 0) of a rectangular grid to the northeast corner (m, n), using only single steps north, northeast, or east. The Delannoy numbers are named after French army officer and amateur mathematician Henri Delannoy.$

In mathematics, Welch bounds are a family of inequalities pertinent to the problem of evenly spreading a set of unit vectors in a vector space. The bounds are important tools in the design and analysis of certain methods in telecommunication engineering, particularly in coding theory. The bounds were originally published in a 1974 paper by L. R. Welch.

In combinatorics, a lattice path $L$ in the $d$ -dimensional integer lattice $of length k with steps in the set S, is a sequence of vectors such that each consecutive difference lies in S . A lattice path may lie in any lattice in, but the integer lattice is most commonly used.$

In mathematics, a transformation of a sequence's generating function provides a method of converting the generating function for one sequence into a generating function enumerating another. These transformations typically involve integral formulas applied to a sequence generating function or weighted sums over the higher-order derivatives of these functions.

References

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.
↑ Arbogast, L. F. A. (1800). Du Calcul des Derivations. Levrault. p. 214.
↑ Shapiro, L. W. (1976). "A Catalan Triangle". Discrete Mathematics. 14 (1): 83–90. doi: 10.1016/0012-365x(76)90009-1 .
↑ Eric W. Weisstein. "Catalan's Triangle". MathWorld − A Wolfram Web Resource. Retrieved March 28, 2012.
↑ Sloane, N. J. A. (ed.). "SequenceA009766(Catalan's triangle)". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation. Retrieved March 28, 2012.
↑ Reuveni, Shlomi (2014). "Catalan's trapezoids". Probability in the Engineering and Informational Sciences. 28 (3): 4391–4396. doi:10.1017/S0269964814000047. S2CID 122765015.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

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

[arbogast-2] Arbogast, L. F. A. (1800). Du Calcul des Derivations. Levrault. p. 214.

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

[Reuveni_PEIS_2014-6] Reuveni, Shlomi (2014). "Catalan's trapezoids". Probability in the Engineering and Informational Sciences. 28 (3): 4391–4396. doi:10.1017/S0269964814000047. S2CID 122765015.

[1]

[2]

[3]

[4]

[5]

[6]