|
|
A355173
|
|
The Fuss-Catalan triangle of order 1, read by rows. Related to binary trees.
|
|
3
|
|
|
1, 0, 1, 0, 1, 2, 0, 1, 3, 5, 0, 1, 4, 9, 14, 0, 1, 5, 14, 28, 42, 0, 1, 6, 20, 48, 90, 132, 0, 1, 7, 27, 75, 165, 297, 429, 0, 1, 8, 35, 110, 275, 572, 1001, 1430, 0, 1, 9, 44, 154, 429, 1001, 2002, 3432, 4862, 0, 1, 10, 54, 208, 637, 1638, 3640, 7072, 11934, 16796
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
The Fuss-Catalan triangle of order m is a regular, (0, 0)-based table recursively defined as follows: Set row(0) = [1] and row(1) = [0, 1]. Now assume row(n-1) already constructed and duplicate the last element of row(n-1). Next apply the cumulative sum m times to this list to get row(n). Here m = 1. (See the Python program for a reference implementation.)
This definition also includes the classical Fuss-Catalan numbers, since T(n, n) = A000108(n), or row 2 in A355262. For m = 2 see A355172 and for m = 3 A355174. More generally, for n >= 1 all Fuss-Catalan sequences (A355262(n, k), k >= 0) are the main diagonals of the Fuss-Catalan triangles of order n - 1.
|
|
LINKS
|
|
|
FORMULA
|
The general formula for the Fuss-Catalan triangles is, for m >= 0 and 0 <= k <= n:
FCT(n, k, m) = (m*(n - k) + m + 1)*(m*n + k - 1)!/((m*n + 1)!*(k - 1)!)) for k > 0 and FCT(n, 0, m) = 0^n. The case considered here is T(n, k) = FCT(n, k, 1).
T(n, k) = (n - k + 2)*(n + k - 1)!/((n + 1)!*(k - 1)!) for k > 0; T(n, 0) = 0^n.
The g.f. of row n of the FC-triangle of order m is 0^n + (x - (m + 1)*x^2) / (1 - x)^(m*n + 2), thus:
T(n, k) = [x^k] (0^n + (x - 2*x^2)/(1 - x)^(n + 2)).
|
|
EXAMPLE
|
Table T(n, k) begins:
[0] [1]
[1] [0, 1]
[2] [0, 1, 2]
[3] [0, 1, 3, 5]
[4] [0, 1, 4, 9, 14]
[5] [0, 1, 5, 14, 28, 42]
[6] [0, 1, 6, 20, 48, 90, 132]
[7] [0, 1, 7, 27, 75, 165, 297, 429]
[8] [0, 1, 8, 35, 110, 275, 572, 1001, 1430]
[9] [0, 1, 9, 44, 154, 429, 1001, 2002, 3432, 4862]
.
Seen as an array reading the diagonals starting from the main diagonal:
[0] 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ... A000108
[1] 0, 1, 3, 9, 28, 90, 297, 1001, 3432, 11934, 41990, ... A000245
[2] 0, 1, 4, 14, 48, 165, 572, 2002, 7072, 25194, 90440, ... A099376
[3] 0, 1, 5, 20, 75, 275, 1001, 3640, 13260, 48450, 177650, ... A115144
[4] 0, 1, 6, 27, 110, 429, 1638, 6188, 23256, 87210, 326876, ... A115145
[5] 0, 1, 7, 35, 154, 637, 2548, 9996, 38760, 149226, 572033, ... A000588
[6] 0, 1, 8, 44, 208, 910, 3808, 15504, 62016, 245157, 961400, ... A115147
[7] 0, 1, 9, 54, 273, 1260, 5508, 23256, 95931, 389367, 1562275, ... A115148
|
|
PROG
|
(Python)
from functools import cache
from itertools import accumulate
@cache
def Trow(n: int) -> list[int]:
if n == 0: return [1]
if n == 1: return [0, 1]
row = Trow(n - 1) + [Trow(n - 1)[n - 1]]
return list(accumulate(row))
for n in range(11): print(Trow(n))
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|