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 0<=k<=n. Each element is equal to the one above plus the one to the left. The sum of each row is equal to the last element of the next row and also equal to the Catalan number C_n. Furthermore, c_(nn)=C_n.

The coefficients c_(nk) also give the number of nonnegative partial sums of n 1s and k -1s, 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)

for n>=k>=2.

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. New York: Elsevier, 1997.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 Web Resource. https://mathworld.wolfram.com/CatalansTriangle.html

Subject classifications