A355173 The Fuss-Catalan triangle of order 1, read by rows. Related to binary trees.

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

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

Table of n, a(n) for n=0..65.

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

A000108 (main diagonal), A000245 (subdiagonal), A002057 (diagonal 2), A000344 (diagonal 3), A000027 (column 2), A000096 (column 3), A071724 (row sums), A000958 (alternating row sums), A262394 (main diagonal of array).

Variants: A009766 (main variant), A030237, A130020.

Cf. A123110 (triangle of order 0), A355172 (triangle of order 2), A355174 (triangle of order 3), A355262 (Fuss-Catalan array).

Cf. A115144, A115145, A000588, A115147, A115148.

Sequence in context: A253672 A367562 A213861 * A108458 A254281 A295682

Adjacent sequences: A355170 A355171 A355172 * A355174 A355175 A355176

Keyword

nonn,tabl

Author

Peter Luschny, Jun 25 2022

Status

approved