Catalan's Triangle
Catalan's triangle is the number triangle
 |
(1)
|
(OEIS A009766) with entries given by
 |
(2)
|
for 
. 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 
. Furthermore, 
.
The coefficients 
also give the number of nonnegative
partial sums of 
1s and 
s, denoted 
by Bailey (1996), who gave the alternate form
 |  |  |
(3)
|
 |  |  |
(4)
|
for 
.
Bailey, D. F. "Counting Arrangements of 1's and 
'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."
Weisstein, Eric W. "Catalan's Triangle." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CatalansTriangle.html
Contact the MathWorld Team
tower of Hanoi