TOPICS
Search

Catalan's Triangle

Catalan's triangle is the number triangle

1 ; 1 1 ; 1 2 2 ; 1 3 5 5 ; 1 4 9 14 14 ; 1 5 14 28 42 42 ; 1 6 20 48 90 132 132
(1)

(OEIS A009766) with entries given by

c_(nk)=((n+k)!(n-k+1))/(k!(n+1)!)
(2)

for nonnegative integers n and k satisfying 0<=k<=n, with rows indexed from n=0. With c_(00)=1 and entries outside the triangle taken as 0, each element in row n>=1 is equal to the one above plus the one to the left. The sum of row n is equal to the last element of the next row and also equal to the Catalan number C_(n+1). Furthermore, c_(nn)=C_n.

The coefficients c_(nk) count distinct sequences formed from n 1s and k -1s and having nonnegative partial sums. These coefficients were denoted {n; k} by Bailey (1996), who gave the alternate form

c_(n0)=1
(3)
c_(nk)=((n+1-k)(n+2)(n+3)...(n+k))/(k!)
(4)

Here the first equation holds for n>=0 and the second for n>=k>=2; also, c_(n1)=n for n>=1.

See also

Bell Triangle, Clark's Triangle, Euler's Number Triangle, Leibniz Harmonic Triangle, Nonnegative Partial Sum, Number Triangle, Pascal's Triangle, Prime Triangle, Seidel-Entringer-Arnold Triangle

Explore with Wolfram|Alpha

References

Bailey, D. F. "Counting Arrangements of 1's and -1's." Math. Mag. 69, 128-131, 1996.Brualdi, R. A. Introductory Combinatorics, 4th ed. Upper Saddle River, NJ: Prentice Hall, 2004.Forder, H. G. "Some Problems in Combinatorics." Math. Gaz. 45, 199-201, 1961.Shapiro, L. W. "A Catalan Triangle." Disc. Math. 14, 83-90, 1976.Sloane, N. J. A. Sequence A009766 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Catalan's Triangle

Cite this as:

Weisstein, Eric W. "Catalan's Triangle." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CatalansTriangle.html

Subject classifications