A355174 The Fuss-Catalan triangle of order 3, read by rows. Related to quartic trees.

1, 0, 1, 0, 1, 4, 0, 1, 7, 22, 0, 1, 10, 49, 140, 0, 1, 13, 85, 357, 969, 0, 1, 16, 130, 700, 2695, 7084, 0, 1, 19, 184, 1196, 5750, 20930, 53820, 0, 1, 22, 247, 1872, 10647, 47502, 166257, 420732, 0, 1, 25, 319, 2755, 17980, 93496, 395560, 1344904, 3362260

Offset: 0

Author

Peter Luschny, Jun 25 2022

Keywords

• nonn
• tabl

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 = 3. (See the Python program for a reference implementation.)

This definition also includes the Fuss-Catalan numbers A002293(n) = T(n, n), row 4 in A355262. For m = 1 see A355173 and for m = 2 A355172. 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.

Examples

			Table T(n, k) begins:
  [0] [1]
  [1] [0, 1]
  [2] [0, 1,  4]
  [3] [0, 1,  7,  22]
  [4] [0, 1, 10,  49,  140]
  [5] [0, 1, 13,  85,  357,   969]
  [6] [0, 1, 16, 130,  700,  2695,  7084]
  [7] [0, 1, 19, 184, 1196,  5750, 20930,  53820]
  [8] [0, 1, 22, 247, 1872, 10647, 47502, 166257,  420732]
  [9] [0, 1, 25, 319, 2755, 17980, 93496, 395560, 1344904, 3362260]
Seen as an array reading the diagonals starting from the main diagonal:
  [0] 1, 1,  4,  22,  140,   969,   7084,   53820,   420732, ...  A002293
  [1] 0, 1,  7,  49,  357,  2695,  20930,  166257,  1344904, ...  A233658
  [2] 0, 1, 10,  85,  700,  5750,  47502,  395560,  3321120, ...  A233667
  [3] 0, 1, 13, 130, 1196, 10647,  93496,  816816,  7128420, ...
  [4] 0, 1, 16, 184, 1872, 17980, 167552, 1535352, 13934752, ...
		

Crossrefs

A002293 (main diagonal), A233658 (subdiagonal), A233667 (diagonal 2), A016777 (column 2), A196678 (row sums).

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

Programs

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(accumulate(accumulate(row))))
for n in range(11): print(Trow(n))

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, 3).

T(n, k) = (3*(n - k) + 4)*(3*n + k - 1)!/((3*n + 1)!*(k - 1)!) for k > 0; T(n, 0) = n^0.

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 - 4*x^2)/(1 - x)^(3*n + 2)).