Catalan triangle

This article needs more work.

Please help by expanding it!

Catalan's triangle is similar to Pascal's triangle, but instead of summing the two terms above, the sum is of the term to the left (on the same row) and the term above, to the right. That is, the recurrence rule is

$T(n,k)=T(n-1,k)+T(n,k-1)\,$.

The row sums are the Catalan numbers, and in fact the last number of the next row gives the sum of the current row

$T(n+1,n+1)=\sum _{k=0}^{n}T(n,k)\,$.

$n\,$								C	a	t	a	l	a	n		t	r	i	a	n	g	l	e						Row sums $\sum _{k=0}^{n}T(n,k)\,$ $=\,$ $\,$ $C(n+1)\,$ $\,$ Catalan numbers (A000108$\scriptstyle (n+1)\,$)
0																	1												1
1																1		1											2
2															1		2		2										5
3														1		3		5		5									14
4													1		4		9		14		14								42
5												1		5		14		28		42		42							132
6											1		6		20		48		90		132		132						429
7										1		7		27		75		165		297		429		429					1430
8									1		8		35		110		275		572		1001		1430		1430				4862
9								1		9		44		154		429		1001		2002		3432		4862		4862			16796
10							1		10		54		208		637		1638		3640		7072		11934		16796		16796		58786
11						1		11		65		273		910		2548		6188		13260		25194		41990		58786		58786	208012
12					1		12		77		350		A005587: $\scriptstyle {\frac {n^{4}+18n^{3}+107n^{2}+210n}{24}}\,$																742900
13				1		13		90		A005586: Number of walks on square lattice $\scriptstyle {\frac {n^{3}+9n^{2}+20n}{6}}\,$																			2674440
14			1		14		A000096: $\scriptstyle {\frac {n^{2}+3n}{2}}\,$																						9694845
15		1		A000027: The positive integers																									35357670
16	A000012: Continued fraction for the golden ratio																												129644790

Catalan's triangle recurrence equation

$T(0,0)=1,\,$

$T(n,k)=T(n-1,k)+T(n,k-1),\ 0\leq k\leq n.\,$

Catalan's triangle formula

$T(n,k)=\sum _{i=0}^{k}{\binom {n}{i}}\,$

and

$T(n,k)-T(n,k-1)={\binom {n}{k}}\,$

Catalan's triangle rows

Catalan's triangle read by rows gives the infinite sequence of finite sequences

{{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, 7, 27, 75, 165, 297, 429, 429}, {1, 8, 35, 110, 275, 572, 1001, 1430, 1430}, ...}

whose concatenation gives the infinite sequence (Cf. A009766)

{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, 7, 27, 75, 165, 297, 429, 429, 1, 8, 35, 110, 275, 572, 1001, 1430, 1430, ...}

Catalan's triangle rows sums

The rows sums give the sequence $\scriptstyle C(n+1),\ n\geq 0\,$, of Catalan numbers (also called Segner numbers)

{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, ...}

The rows sums may be computed with the formula

$\sum _{k=0}^{n}T(n,k)=C(n+1)={\frac {1}{n+2}}{\binom {2n+2}{n+1}}={\frac {(2n+2)!}{(n+1)!(n+2)!}},$

where $\scriptstyle C(n)\,$ is the $\scriptstyle n\,$^th Catalan number.

The generating function is

$G_{\{\sum _{k=0}^{n}T(n,k)\}}(x)=G_{\{C(n+1)\}}(x)={\frac {G_{\{C(n)\}}(x)-G_{\{C(0)\}}(x)}{x}}={\frac {1-{\sqrt {1-4x}}}{2x^{2}}}-{\frac {1}{x}}\,$

where

$G_{\{C(n)\}}(x)={\frac {1-{\sqrt {1-4x}}}{2x}}\,$

is the generating function of the Catalan numbers.

Catalan's triangle rows alternating sign sums

$\sum _{k=0}^{n}(-1)^{k}\ T(n,k)=~?\,$

Catalan's triangle rising diagonals

The table gives the $\scriptstyle j\,$^th member, $\scriptstyle j\,\geq \,0,\,$ of the $\scriptstyle i\,$^th, $\scriptstyle i\,\geq \,0,\,$ rising diagonal (0 for leftmost.)

Catalan's triangle rising diagonals sequences

$i\,$	$T(i+j,i),\ j\geq 0\,$ sequences	A-number
0	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...}	A000012($\scriptstyle j\,$)
1	{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, ...}	A000027($\scriptstyle j+1\,$)
2	{2, 5, 9, 14, 20, 27, 35, 44, 54, 65, 77, 90, 104, 119, 135, 152, 170, 189, 209, 230, 252, 275, 299, 324, 350, 377, 405, 434, 464, 495, 527, 560, 594, 629, 665, ...}	A000096($\scriptstyle j+1\,$)
3	{5, 14, 28, 48, 75, 110, 154, 208, 273, 350, 440, 544, 663, 798, 950, 1120, 1309, 1518, 1748, 2000, 2275, 2574, 2898, 3248, 3625, 4030, 4464, 4928, 5423, ...}	A005586($\scriptstyle j+1\,$)
4	{14, 42, 90, 165, 275, 429, 637, 910, 1260, 1700, 2244, 2907, 3705, 4655, 5775, 7084, 8602, 10350, 12350, 14625, 17199, 20097, 23345, 26970, 31000, 35464, ...}	A005587($\scriptstyle j+1\,$)
5	{42, 132, 297, 572, 1001, 1638, 2548, 3808, 5508, 7752, 10659, 14364, 19019, 24794, 31878, 40480, 50830, 63180, 77805, 95004, 115101, 138446, 165416, ...}	A005557($\scriptstyle j\,$)
6	{132, 429, 1001, 2002, 3640, 6188, 9996, 15504, 23256, 33915, 48279, 67298, 92092, 123970, 164450, 215280, 278460, 356265, 451269, 566370, 704816, ...}	A064059($\scriptstyle j\,$)
7	{429, 1430, 3432, 7072, 13260, 23256, 38760, 62016, 95931, 144210, 211508, 303600, 427570, 592020, 807300, 1085760, 1442025, 1893294, 2459664, ...}	A064061($\scriptstyle j\,$)
8	{1430, 4862, 11934, 25194, 48450, 87210, 149226, 245157, 389367, 600875, 904475, 1332045, 1924065, 2731365, 3817125, 5259150, 7152444, ...}	A124087($\scriptstyle j+15\,$)
9	{4862, 16796, 41990, 90440, 177650, 326876, 572033, 961400, 1562275, 2466750, 3798795, 5722860, 8454225, 12271350, 17530500, 24682944, ...}	A124088($\scriptstyle j+17\,$)
10	{16796, ...}	A??????
11	{58786, ...}	A??????
12	{208012, ...}	A??????

Catalan's triangle rising diagonals formulae and values

$i\,$	Formulae $T(i+j,i)=\,$	Generating function $G_{\{T(i+j,i)\}}(x)=\,$	Differences $T(i+j,i)-T(i+j-1,i)=\,$	Partial sums $\sum _{j=0}^{m}{T(i+j,i)}=\,$	Partial sums of reciprocals $\sum _{j=0}^{m}{1 \over {T(i+j,i)}}=\,$	Sum of Reciprocals $\sum _{j=0}^{\infty }{1 \over {T(i+j,i)}}=\,$
0
1
2
3
4
5
6
7
8
9
10

Catalan's triangle falling diagonals

The table gives the $\scriptstyle j\,$^th member, $\scriptstyle j\,\geq \,0,\,$ of the $\scriptstyle i\,$^th, $\scriptstyle i\,\geq \,0,\,$ falling diagonal (0 for rightmost.)

Catalan's triangle falling diagonals sequences

$i\,$	$T(i+j,j),\ j\geq 0\,$ sequences	A-number
0	{1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, ...}	A000108($\scriptstyle j\,$)
1	{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, ...}	A000108($\scriptstyle j+1\,$)
2	{1, 3, 9, 28, 90, 297, 1001, 3432, 11934, 41990, 149226, 534888, 1931540, 7020405, 25662825, 94287120, 347993910, 1289624490, 4796857230, 17902146600, ...}	A000245($\scriptstyle j+1\,$)
3	{1, 4, 14, 48, 165, 572, 2002, 7072, 25194, 90440, 326876, 1188640, 4345965, 15967980, 58929450, 218349120, 811985790, 3029594040, 11338026180, ...}	A002057($\scriptstyle j\,$)
4	{1, 5, 20, 75, 275, 1001, 3640, 13260, 48450, 177650, 653752, 2414425, 8947575, 33266625, 124062000, 463991880, 1739969550, 6541168950, 24647883000, ...}	A000344($\scriptstyle j+2\,$)
5	{1, 6, 27, 110, 429, 1638, 6188, 23256, 87210, 326876, 1225785, 4601610, 17298645, 65132550, 245642760, 927983760, 3511574910, 13309856820, ...}	A003517($\scriptstyle j+2\,$)
6	{1, 7, 35, 154, 637, 2548, 9996, 38760, 149226, 572033, 2187185, 8351070, 31865925, 121580760, 463991880, 1771605360, 6768687870, 25880277150, ...}	A000588($\scriptstyle j+3\,$)
7	{1, 8, 44, 208, 910, 3808, 15504, 62016, 245157, 961400, 3749460, 14567280, 56448210, 218349120, 843621600, 3257112960, 12570420330, 48507033744, ...}	A003518($\scriptstyle j+3\,$)
8	{1, 9, 54, 273, 1260, 5508, 23256, 95931, 389367, 1562275, 6216210, 24582285, 96768360, 379629720, 1485507600, 5801732460, 22626756594, 88152205554, ...}	A001392($\scriptstyle j+4\,$)
9	{1, 10, 65, 350, 1700, 7752, 33915, 144210, 600875, 2466750, 10015005, 40320150, 161280600, 641886000, 2544619500, 10056336264, 39645171810, ...}	A003519($\scriptstyle j+4\,$)
10	{1, 11, 77, 440, 2244, 10659, 48279, 211508, 904475, 3798795, 15737865, 64512240, 262256280, 1059111900, 4254603804, 17018415216, 67837293986, ...}	A000589($\scriptstyle j+5\,$)
11	{1, 12, 90, ...}	A??????
12	{1, 13, ...}	A??????

Catalan's triangle falling diagonals formulae and values

$i\,$	Formulae $T(i+j,j)=\,$	Generating function $G_{\{T(i+j,j)\}}(x)=\,$	Differences $T(i+j,j)-T(i+j-1,j)=\,$	Partial sums $\sum _{j=0}^{m}{T(i+j,j)}=\,$	Partial sums of reciprocals $\sum _{j=0}^{m}{1 \over {T(i+j,j)}}=\,$	Sum of Reciprocals $\sum _{j=0}^{\infty }{1 \over {T(i+j,j)}}=\,$
0
1
2
3
4
5
6
7
8
9
10

Using Catalan's triangle to rank & unrank Dyck words/paths

Catalan's triangle can be used to rank and unrank Dyck words or paths (or any other combinatorial interpretation of Catalan numbers for which a bijective correspondence with the former can be found). This has been explained for example by Donald Kreher and Douglas Stinson, and Frank Ruskey in his thesis.

Code

To do: copy from [[1]] all appropriate parts, Maple and Scheme-code, etc.

See also

• A124061 Multiplicative encoding of Catalan's triangle: Product $\scriptstyle p(i+1)^{T(n,i)}\,$.