This site is supported by donations to The OEIS Foundation.

Catalan triangle

From OeisWiki

Jump to: navigation, search

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 + 18 n^3 + 107 n^2 + 210 n}{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


Contents

Catalan's triangle recurrence equation

T(0,0) = 1, \,
T(n, k) = T(n - 1, k) + T(n, k - 1),\ 0 \le k \le 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 \ge 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 \,\ge\, 0, \, of the \scriptstyle i \,th, \scriptstyle i \,\ge\, 0, \, rising diagonal (0 for leftmost.)

Catalan's triangle rising diagonals sequences
i \, T(i+j,i),\ j \ge 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 \,\ge\, 0, \, of the \scriptstyle i \,th, \scriptstyle i \,\ge\, 0, \, falling diagonal (0 for rightmost.)

Catalan's triangle falling diagonals sequences
i \, T(i+j,j),\ j \ge 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


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

Notes

  1. Kreher and Stinson, Combinatorial Algorithms, Generation, Enumeration and Search (CAGES), CRC Press, 1998.
  2. F. Ruskey, Algorithmic Solution of Two Combinatorial Problems, Thesis, Department of Applied Physics and Information Science, University of Victoria, 1978.
Personal tools