A355174 -id:A355174 - cp's OEIS frontend

A355262 Array of Fuss-Catalan numbers read by ascending antidiagonals, A(n, k) = binomial(kn + 1, k)/(kn + 1).

1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 3, 5, 1, 0, 1, 1, 4, 12, 14, 1, 0, 1, 1, 5, 22, 55, 42, 1, 0, 1, 1, 6, 35, 140, 273, 132, 1, 0, 1, 1, 7, 51, 285, 969, 1428, 429, 1, 0, 1, 1, 8, 70, 506, 2530, 7084, 7752, 1430, 1, 0

Offset: 0

Peter Luschny, Jun 26 2022

An alternative definition is: the Fuss-Catalan sequences (A(n, k), k >= 0 ) are the main diagonals of the Fuss-Catalan triangles of order n - 1. See A355173 for the definition of a Fuss-Catalan triangle.

			Array A(n, k) begins:
[0] 1, 1, 0,   0,    0,     0,      0,       0,         0, ...  A019590
[1] 1, 1, 1,   1,    1,     1,      1,       1,         1, ...  A000012
[2] 1, 1, 2,   5,   14,    42,    132,     429,      1430, ...  A000108
[3] 1, 1, 3,  12,   55,   273,   1428,    7752,     43263, ...  A001764
[4] 1, 1, 4,  22,  140,   969,   7084,   53820,    420732, ...  A002293
[5] 1, 1, 5,  35,  285,  2530,  23751,  231880,   2330445, ...  A002294
[6] 1, 1, 6,  51,  506,  5481,  62832,  749398,   9203634, ...  A002295
[7] 1, 1, 7,  70,  819, 10472, 141778, 1997688,  28989675, ...  A002296
[8] 1, 1, 8,  92, 1240, 18278, 285384, 4638348,  77652024, ...  A007556
[9] 1, 1, 9, 117, 1785, 29799, 527085, 9706503, 184138713, ...  A062994

N. I. Fuss, Solutio quaestionis, quot modis polygonum n laterum in polygona m laterum, per diagonales resolvi queat, Nova Acta Academiae Scientiarum Imperialis Petropolitanae, vol.9 (1791), 243-251.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, MA, 1990, (Eqs. 5.70, 7.66, and sec. 7.5, example 5).

Per Alexandersson, Frether Getachew Kebede, Samuel Asefa Fufa, and Dun Qiu, Pattern-Avoidance and Fuss-Catalan Numbers, J. Int. Seq. (2023) Vol. 26, Art. 23.4.2.
Joerg Arndt, Matters Computational (The Fxtbook), pp. 337-338.
Jean-Luc Baril, Mireille Bousquet-Mélou, Sergey Kirgizov, and Mehdi Naima, The ascent lattice on Dyck paths, arXiv:2409.15982 [math.CO], 2024. See p. 6.
Jean-Christophe Aval, Multivariate Fuss-Catalan Numbers, arXiv:0711.0906v1, Discrete Math., 308 (2008), 4660-4669.
Thomas A. Dowling, Catalan Numbers, Chapter 7.
D. E. Knuth, Convolution polynomials, arXiv:math/9207221 [math.CA]; Mathematica J. 2.1 (1992), no. 4, 67-78.
Donald Knuth's 20th Annual Christmas Tree Lecture, (3/2)-ary Trees, Stanford Online, Video 2014.
Wojciech Młotkowski, Fuss-Catalan Numbers in Noncommutative Probability, Docum. Math. 15:939-955, (2010).
Wikipedia, Fuss-Catalan number.

Cf. A091144 (main diagonal), A019590, A000012, A000108, A001764, A002293, A002294, A002295, A002296, A007556, A062994.
Variants: A062993, A070914.
Fuss-Catalan triangles: A123110 (order 0), A355173 (order 1), A355172 (order 2), A355174 (order 3).

A := (n, k) -> binomial(k*n + 1, k)/(k*n + 1):
for n from 0 to 9 do seq(A(n, k), k = 0..8) od;

(* See the Knuth references. In the christmas lecture Knuth has fun calculating the Fuss-Catalan development of Pi and i. *)
B[t_, n_] := Sum[Binomial[t k+1, k] z^k / (t k+1), {k, 0, n-1}] + O[z]^n
Table[CoefficientList[B[n, 9], z], {n, 0, 9}] // TableForm

A(n, k) = (1/k!) * Product_{j=1..k-1} (k*n + 1 - j).
A(n, k) = (binomial(k*n, k) + binomial(k*n, k-1)) / (k*n + 1).
Let B(t, z) = Sum_{k>=0} binomial(k*t + 1, k)*z^k / (k*t + 1), then
A(n, k) = [z^k] B(n, z).

A355172 The Fuss-Catalan triangle of order 2, read by rows. Related to ternary trees.

Original entry on oeis.org

1, 0, 1, 0, 1, 3, 0, 1, 5, 12, 0, 1, 7, 25, 55, 0, 1, 9, 42, 130, 273, 0, 1, 11, 63, 245, 700, 1428, 0, 1, 13, 88, 408, 1428, 3876, 7752, 0, 1, 15, 117, 627, 2565, 8379, 21945, 43263, 0, 1, 17, 150, 910, 4235, 15939, 49588, 126500, 246675

Offset: 0

Peter Luschny, Jun 25 2022

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

This definition also includes the Fuss-Catalan numbers A001764(n) = T(n, n), or row 3 in A355262. For m = 1 see A355173 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.

			Table T(n, k) begins:
  [0] [1]
  [1] [0, 1]
  [2] [0, 1,  3]
  [3] [0, 1,  5, 12]
  [4] [0, 1,  7, 25,  55]
  [5] [0, 1,  9, 42, 130,  273]
  [6] [0, 1, 11, 63, 245,  700, 1428]
  [7] [0, 1, 13, 88, 408, 1428, 3876, 7752]
Seen as an array reading the diagonals starting from the main diagonal:
  [0] 1, 1,  3, 12,  55,  273,  1428,   7752,   43263,  246675, ...  A001764
  [1] 0, 1,  5, 25, 130,  700,  3876,  21945,  126500,  740025, ...  A102893
  [2] 0, 1,  7, 42, 245, 1428,  8379,  49588,  296010, 1781325, ...  A102594
  [3] 0, 1,  9, 63, 408, 2565, 15939,  98670,  610740, 3786588, ...  A230547
  [4] 0, 1, 11, 88, 627, 4235, 27830, 180180, 1157013, 7396972, ...

A001764 (main diagonal), A102893 (subdiagonal), A102594 (diagonal 2), A230547 (diagonal 3), A005408 (column 2), A071355 (column 3), A006629 (row sums), A143603 (variant).

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

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

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, 2).
T(n, k) = (2*n - 2*k + 3)*(2*n + k - 1)!/((2*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 - 3*x^2)/(1 - x)^(2*n + 2)).

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

Original entry on oeis.org

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

Peter Luschny, Jun 25 2022

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.

			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

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.

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))

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

cp's OEIS Frontend

A355262 Array of Fuss-Catalan numbers read by ascending antidiagonals, A(n, k) = binomial(kn + 1, k)/(kn + 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A355172 The Fuss-Catalan triangle of order 2, read by rows. Related to ternary trees.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

cp's OEIS Frontend

A355262 Array of Fuss-Catalan numbers read by ascending antidiagonals, A(n, k) = binomial(k*n + 1, k)/(k*n + 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A355172 The Fuss-Catalan triangle of order 2, read by rows. Related to ternary trees.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

A355262 Array of Fuss-Catalan numbers read by ascending antidiagonals, A(n, k) = binomial(kn + 1, k)/(kn + 1).