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

%I #26 Sep 29 2024 09:19:47

%S 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,

%T 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,

%U 8,70,506,2530,7084,7752,1430,1,0

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

%C 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.

%D 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.

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

%H Per Alexandersson, Frether Getachew Kebede, Samuel Asefa Fufa, and Dun Qiu, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Getachew/get3.html">Pattern-Avoidance and Fuss-Catalan Numbers</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.2.

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 337-338.

%H Jean-Luc Baril, Mireille Bousquet-Mélou, Sergey Kirgizov, and Mehdi Naima, <a href="https://arxiv.org/abs/2409.15982">The ascent lattice on Dyck paths</a>, arXiv:2409.15982 [math.CO], 2024. See p. 6.

%H Jean-Christophe Aval, <a href="https://arxiv.org/abs/0711.0906">Multivariate Fuss-Catalan Numbers</a>, arXiv:0711.0906v1, Discrete Math., 308 (2008), 4660-4669.

%H Thomas A. Dowling, <a href="https://docplayer.net/6827054-Catalan-numbers-thomas-a-dowling-department-of-mathematics-ohio-state-uni-versity.html">Catalan Numbers</a>, Chapter 7.

%H D. E. Knuth, <a href="https://arxiv.org/abs/math/9207221">Convolution polynomials</a>, arXiv:math/9207221 [math.CA]; Mathematica J. 2.1 (1992), no. 4, 67-78.

%H Donald Knuth's 20th Annual Christmas Tree Lecture, <a href="https://www.youtube.com/watch?v=P4AaGQIo0HY">(3/2)-ary Trees</a>, Stanford Online, Video 2014.

%H Wojciech Młotkowski, <a href="https://www.math.uni-bielefeld.de/documenta/vol-15/28.pdf">Fuss-Catalan Numbers in Noncommutative Probability</a>, Docum. Math. 15:939-955, (2010).

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Fuss%E2%80%93Catalan_number">Fuss-Catalan number</a>.

%F A(n, k) = (1/k!) * Product_{j=1..k-1} (k*n + 1 - j).

%F A(n, k) = (binomial(k*n, k) + binomial(k*n, k-1)) / (k*n + 1).

%F Let B(t, z) = Sum_{k>=0} binomial(k*t + 1, k)*z^k / (k*t + 1), then

%F A(n, k) = [z^k] B(n, z).

%e Array A(n, k) begins:

%e [0] 1, 1, 0, 0, 0, 0, 0, 0, 0, ... A019590

%e [1] 1, 1, 1, 1, 1, 1, 1, 1, 1, ... A000012

%e [2] 1, 1, 2, 5, 14, 42, 132, 429, 1430, ... A000108

%e [3] 1, 1, 3, 12, 55, 273, 1428, 7752, 43263, ... A001764

%e [4] 1, 1, 4, 22, 140, 969, 7084, 53820, 420732, ... A002293

%e [5] 1, 1, 5, 35, 285, 2530, 23751, 231880, 2330445, ... A002294

%e [6] 1, 1, 6, 51, 506, 5481, 62832, 749398, 9203634, ... A002295

%e [7] 1, 1, 7, 70, 819, 10472, 141778, 1997688, 28989675, ... A002296

%e [8] 1, 1, 8, 92, 1240, 18278, 285384, 4638348, 77652024, ... A007556

%e [9] 1, 1, 9, 117, 1785, 29799, 527085, 9706503, 184138713, ... A062994

%p A := (n, k) -> binomial(k*n + 1, k)/(k*n + 1):

%p for n from 0 to 9 do seq(A(n, k), k = 0..8) od;

%t (* See the Knuth references. In the christmas lecture Knuth has fun calculating the Fuss-Catalan development of Pi and i. *)

%t B[t_, n_] := Sum[Binomial[t k+1, k] z^k / (t k+1), {k, 0, n-1}] + O[z]^n

%t Table[CoefficientList[B[n, 9], z], {n, 0, 9}] // TableForm

%Y Cf. A091144 (main diagonal), A019590, A000012, A000108, A001764, A002293, A002294, A002295, A002296, A007556, A062994.

%Y Variants: A062993, A070914.

%Y Fuss-Catalan triangles: A123110 (order 0), A355173 (order 1), A355172 (order 2), A355174 (order 3).

%K nonn,tabl

%O 0,13

%A _Peter Luschny_, Jun 26 2022