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 .

REFERENCES:

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