This site is supported by donations to The OEIS Foundation.
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
- .
The row sums are the Catalan numbers, and in fact the last number of the next row gives the sum of the current row
- .
C | a | t | a | l | a | n | t | r | i | a | n | g | l | e | Row sums
(A000108) | ||||||||||||||
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: | 742900 | |||||||||||||||||||||||
13 | 1 | 13 | 90 | A005586: Number of walks on square lattice | 2674440 | ||||||||||||||||||||||||
14 | 1 | 14 | A000096: | 9694845 | |||||||||||||||||||||||||
15 | 1 | A000027: The positive integers | 35357670 | ||||||||||||||||||||||||||
16 | A000012: Continued fraction for the golden ratio | 129644790 |
Contents
- 1 Catalan's triangle recurrence equation
- 2 Catalan's triangle formula
- 3 Catalan's triangle rows
- 4 Catalan's triangle rising diagonals
- 5 Catalan's triangle falling diagonals
- 6 Catalan's triangle central elements
- 7 Catalan's triangle (slope 1/2) rising diagonals
- 8 Catalan's triangle (slope -1/2) falling diagonals
- 9 Using Catalan's triangle to rank & unrank Dyck words/paths
- 10 Code
- 11 See also
- 12 Notes
Catalan's triangle recurrence equation
Catalan's triangle formula
and
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 , 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
where is the th Catalan number.
The generating function is
where
is the generating function of the Catalan numbers.
Catalan's triangle rows alternating sign sums
Catalan's triangle rising diagonals
The table gives the th member, of the th, rising diagonal (0 for leftmost.)
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() |
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() |
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() |
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() |
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() |
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() |
6 | {132, 429, 1001, 2002, 3640, 6188, 9996, 15504, 23256, 33915, 48279, 67298, 92092, 123970, 164450, 215280, 278460, 356265, 451269, 566370, 704816, ...} | A064059() |
7 | {429, 1430, 3432, 7072, 13260, 23256, 38760, 62016, 95931, 144210, 211508, 303600, 427570, 592020, 807300, 1085760, 1442025, 1893294, 2459664, ...} | A064061() |
8 | {1430, 4862, 11934, 25194, 48450, 87210, 149226, 245157, 389367, 600875, 904475, 1332045, 1924065, 2731365, 3817125, 5259150, 7152444, ...} | A124087() |
9 | {4862, 16796, 41990, 90440, 177650, 326876, 572033, 961400, 1562275, 2466750, 3798795, 5722860, 8454225, 12271350, 17530500, 24682944, ...} | A124088() |
10 | {16796, ...} | A?????? |
11 | {58786, ...} | A?????? |
12 | {208012, ...} | A?????? |
Formulae
|
Generating
function
|
Differences
|
Partial sums
|
Partial sums of reciprocals
|
Sum of Reciprocals
| |
---|---|---|---|---|---|---|
0 | ||||||
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
5 | ||||||
6 | ||||||
7 | ||||||
8 | ||||||
9 | ||||||
10 |
Catalan's triangle falling diagonals
The table gives the th member, of the th, falling diagonal (0 for rightmost.)
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() |
1 | {1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, ...} | A000108() |
2 | {1, 3, 9, 28, 90, 297, 1001, 3432, 11934, 41990, 149226, 534888, 1931540, 7020405, 25662825, 94287120, 347993910, 1289624490, 4796857230, 17902146600, ...} | A000245() |
3 | {1, 4, 14, 48, 165, 572, 2002, 7072, 25194, 90440, 326876, 1188640, 4345965, 15967980, 58929450, 218349120, 811985790, 3029594040, 11338026180, ...} | A002057() |
4 | {1, 5, 20, 75, 275, 1001, 3640, 13260, 48450, 177650, 653752, 2414425, 8947575, 33266625, 124062000, 463991880, 1739969550, 6541168950, 24647883000, ...} | A000344() |
5 | {1, 6, 27, 110, 429, 1638, 6188, 23256, 87210, 326876, 1225785, 4601610, 17298645, 65132550, 245642760, 927983760, 3511574910, 13309856820, ...} | A003517() |
6 | {1, 7, 35, 154, 637, 2548, 9996, 38760, 149226, 572033, 2187185, 8351070, 31865925, 121580760, 463991880, 1771605360, 6768687870, 25880277150, ...} | A000588() |
7 | {1, 8, 44, 208, 910, 3808, 15504, 62016, 245157, 961400, 3749460, 14567280, 56448210, 218349120, 843621600, 3257112960, 12570420330, 48507033744, ...} | A003518() |
8 | {1, 9, 54, 273, 1260, 5508, 23256, 95931, 389367, 1562275, 6216210, 24582285, 96768360, 379629720, 1485507600, 5801732460, 22626756594, 88152205554, ...} | A001392() |
9 | {1, 10, 65, 350, 1700, 7752, 33915, 144210, 600875, 2466750, 10015005, 40320150, 161280600, 641886000, 2544619500, 10056336264, 39645171810, ...} | A003519() |
10 | {1, 11, 77, 440, 2244, 10659, 48279, 211508, 904475, 3798795, 15737865, 64512240, 262256280, 1059111900, 4254603804, 17018415216, 67837293986, ...} | A000589() |
11 | {1, 12, 90, ...} | A?????? |
12 | {1, 13, ...} | A?????? |
Formulae
|
Generating
function
|
Differences
|
Partial sums
|
Partial sums of reciprocals
|
Sum of Reciprocals
| |
---|---|---|---|---|---|---|
0 | ||||||
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
5 | ||||||
6 | ||||||
7 | ||||||
8 | ||||||
9 | ||||||
10 |
Catalan's triangle central elements
Catalan's triangle (slope 1/2) rising diagonals
Catalan's triangle (slope 1/2) rising diagonals sums
Catalan's triangle (slope 1/2) rising diagonals alternating sign sums
Catalan's triangle (slope -1/2) falling diagonals
Catalan's triangle (slope -1/2) falling diagonals sums
Catalan's triangle (slope -1/2) falling diagonals alternating sign sums
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,[1] and Frank Ruskey in his thesis.[2]
Code
To do: copy from [[1]] all appropriate parts, Maple and Scheme-code, etc.
See also
- A124061 Multiplicative encoding of Catalan's triangle: Product .
Notes
- ↑ Kreher and Stinson, Combinatorial Algorithms, Generation, Enumeration and Search (CAGES), CRC Press, 1998.
- ↑ F. Ruskey, Algorithmic Solution of Two Combinatorial Problems, Thesis, Department of Applied Physics and Information Science, University of Victoria, 1978.