login
Array read by antidiagonals: T(n,k) = k-Modular Catalan numbers C_{n,k} (n >= 0, k > 0).
8

%I #35 Oct 14 2022 05:35:39

%S 1,1,1,1,1,1,1,1,2,1,1,1,2,4,1,1,1,2,5,8,1,1,1,2,5,13,16,1,1,1,2,5,14,

%T 35,32,1,1,1,2,5,14,41,96,64,1,1,1,2,5,14,42,124,267,128,1,1,1,2,5,14,

%U 42,131,384,750,256,1,1,1,2,5,14,42,132,420,1210,2123,512,1

%N Array read by antidiagonals: T(n,k) = k-Modular Catalan numbers C_{n,k} (n >= 0, k > 0).

%C Definition: Given a primitive k-th root of unity w, a binary operation a*b=a+wb, and sufficiently general fixed complex numbers x_0, ..., x_n, the k-modular Catalan numbers C_{n,k} enumerate parenthesizations of x_0*x_1*...*x_n that give distinct values.

%C Theorem: C_{n,k} enumerates the following objects:

%C (1) binary trees with n internal nodes avoiding a certain subtree (i.e., comb_k^{+1}),

%C (2) plane trees with n+1 nodes whose non-root nodes have degree less than k,

%C (3) Dyck paths of length 2n avoiding a down-step followed immediately by k consecutive up-steps,

%C (4) partitions with n nonnegative parts bounded by the staircase partition (n-1,n-2,...,1,0) such that each positive number appears fewer than k times,

%C (5) standard 2-by-n Young tableaux whose top row avoids contiguous labels of the form i,j+1,j+2,...,j+k for all i<j, and

%C (6) permutations of {1,2,...,n} avoiding 1-3-2 and 23...(k+1)1.

%C Columns of the array converge rowwise to A000108. The diagonal k=n-1 is A001453. - _Andrey Zabolotskiy_, Dec 02 2017

%H Andrew Howroyd, <a href="/A295679/b295679.txt">Table of n, a(n) for n = 0..1274</a>

%H Nickolas Hein, Jia Huang, <a href="https://doi.org/10.1016/j.ejc.2016.11.004">Modular Catalan Numbers</a>, European Journal of Combinatorics, 61 (2017), 197-218, <a href="http://arxiv.org/abs/1508.01688">arXiv:1508.01688</a> [math.CO], 2015-2016.

%F G.f. of column k: 1/(1-G(x)) where G(x) is the reversion of x*(1-x)/(1-x^k).

%e Array begins (n >= 0, k > 0):

%e ======================================================

%e n\k| 1 2 3 4 5 6 7 8 9 10

%e ---|--------------------------------------------------

%e 0 | 1 1 1 1 1 1 1 1 1 1 ...

%e 1 | 1 1 1 1 1 1 1 1 1 1 ...

%e 2 | 1 2 2 2 2 2 2 2 2 2 ...

%e 3 | 1 4 5 5 5 5 5 5 5 5 ...

%e 4 | 1 8 13 14 14 14 14 14 14 14 ...

%e 5 | 1 16 35 41 42 42 42 42 42 42 ...

%e 6 | 1 32 96 124 131 132 132 132 132 132 ...

%e 7 | 1 64 267 384 420 428 429 429 429 429 ...

%e 8 | 1 128 750 1210 1375 1420 1429 1430 1430 1430 ...

%e 9 | 1 256 2123 3865 4576 4796 4851 4861 4862 4862 ...

%e ...

%p A295679 := proc(n,k)

%p if n = 0 then

%p 1;

%p else

%p add((-1)^j/n*binomial(n,j)*binomial(2*n-j*k,n+1),j=0..(n-1)/k) ;

%p end if ;

%p end proc:

%p seq(seq( A295679(n,d-n),n=0..d-1),d=1..12) ; # _R. J. Mathar_, Oct 14 2022

%t rows = cols = 12;

%t col[k_] := Module[{G}, G = InverseSeries[x*(1-x)/(1-x^k) + O[x]^cols, x]; CoefficientList[1/(1 - G), x]];

%t A = Array[col, cols];

%t T[n_, k_] := A[[k, n+1]];

%t Table[T[n-k+1, k], {n, 0, rows-1}, {k, n+1, 1, -1}] // Flatten (* _Jean-François Alcover_, Dec 05 2017, adapted from PARI *)

%o (PARI)

%o T(n,k)=polcoeff(1/(1-serreverse(x*(1-x)/(1-x^k) + O(x^max(2,n+1)))), n);

%o for(n=0, 10, for(k=1, 10, print1(T(n, k), ", ")); print);

%Y Columns 3..9 are A005773, A159772, A261588, A261589, A261590, A261591, A261592.

%Y Cf. A288942, A000108, A001453.

%K nonn,tabl,easy

%O 0,9

%A _Andrew Howroyd_, Nov 30 2017