This site is supported by donations to The OEIS Foundation.

# Catalan triangle

(Redirected from Catalan's triangle)

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
${\displaystyle 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

${\displaystyle T(n+1,n+1)=\sum _{k=0}^{n}T(n,k)\,}$.
 ${\displaystyle n\,}$ C a t a l a n t r i a n g l e Row sums ${\displaystyle \sum _{k=0}^{n}T(n,k)\,}$ ${\displaystyle =\,}$ ${\displaystyle \,}$ ${\displaystyle C(n+1)\,}$ ${\displaystyle \,}$ (A000108${\displaystyle \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: ${\displaystyle \scriptstyle {\frac {n^{4}+18n^{3}+107n^{2}+210n}{24}}\,}$ 742900 13 1 13 90 A005586: Number of walks on square lattice ${\displaystyle \scriptstyle {\frac {n^{3}+9n^{2}+20n}{6}}\,}$ 2674440 14 1 14 A000096: ${\displaystyle \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

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

## Catalan's triangle formula

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

and

${\displaystyle 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 ${\displaystyle \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

${\displaystyle \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 ${\displaystyle \scriptstyle C(n)\,}$ is the ${\displaystyle \scriptstyle n\,}$th Catalan number.

The generating function is

${\displaystyle 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

${\displaystyle 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

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

## Catalan's triangle rising diagonals

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

Catalan's triangle rising diagonals sequences
${\displaystyle i\,}$ ${\displaystyle 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(${\displaystyle \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(${\displaystyle \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(${\displaystyle \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(${\displaystyle \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(${\displaystyle \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(${\displaystyle \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(${\displaystyle \scriptstyle j\,}$)
7 {429, 1430, 3432, 7072, 13260, 23256, 38760, 62016, 95931, 144210, 211508, 303600, 427570, 592020, 807300, 1085760, 1442025, 1893294, 2459664, ...} A064061(${\displaystyle \scriptstyle j\,}$)
8 {1430, 4862, 11934, 25194, 48450, 87210, 149226, 245157, 389367, 600875, 904475, 1332045, 1924065, 2731365, 3817125, 5259150, 7152444, ...} A124087(${\displaystyle \scriptstyle j+15\,}$)
9 {4862, 16796, 41990, 90440, 177650, 326876, 572033, 961400, 1562275, 2466750, 3798795, 5722860, 8454225, 12271350, 17530500, 24682944, ...} A124088(${\displaystyle \scriptstyle j+17\,}$)
10 {16796, ...} A??????
11 {58786, ...} A??????
12 {208012, ...} A??????

Catalan's triangle rising diagonals formulae and values
${\displaystyle i\,}$ Formulae

${\displaystyle T(i+j,i)=\,}$

Generating

function

${\displaystyle G_{\{T(i+j,i)\}}(x)=\,}$

Differences

${\displaystyle T(i+j,i)-T(i+j-1,i)=\,}$

Partial sums

${\displaystyle \sum _{j=0}^{m}{T(i+j,i)}=\,}$

Partial sums of reciprocals

${\displaystyle \sum _{j=0}^{m}{1 \over {T(i+j,i)}}=\,}$

Sum of Reciprocals

${\displaystyle \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 ${\displaystyle \scriptstyle j\,}$th member, ${\displaystyle \scriptstyle j\,\geq \,0,\,}$ of the ${\displaystyle \scriptstyle i\,}$th, ${\displaystyle \scriptstyle i\,\geq \,0,\,}$ falling diagonal (0 for rightmost.)

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

Catalan's triangle falling diagonals formulae and values
${\displaystyle i\,}$ Formulae

${\displaystyle T(i+j,j)=\,}$

Generating

function

${\displaystyle G_{\{T(i+j,j)\}}(x)=\,}$

Differences

${\displaystyle T(i+j,j)-T(i+j-1,j)=\,}$

Partial sums

${\displaystyle \sum _{j=0}^{m}{T(i+j,j)}=\,}$

Partial sums of reciprocals

${\displaystyle \sum _{j=0}^{m}{1 \over {T(i+j,j)}}=\,}$

Sum of Reciprocals

${\displaystyle \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,[1] and Frank Ruskey in his thesis.[2]

## Code

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

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