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

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, 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, 42, 131, 384, 750, 256, 1, 1, 1, 2, 5, 14, 42, 132, 420, 1210, 2123, 512, 1

Offset

0,9

Comments

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.

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

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

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

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

(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,

(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

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

Columns of the array converge rowwise to A000108. The diagonal k=n-1 is A001453. - Andrey Zabolotskiy, Dec 02 2017

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1274

Nickolas Hein, Jia Huang, Modular Catalan Numbers, European Journal of Combinatorics, 61 (2017), 197-218, arXiv:1508.01688 [math.CO], 2015-2016.

Formula

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

Example

Array begins (n >= 0, k > 0):
======================================================
n\k| 1   2    3    4    5    6    7    8    9   10
---|--------------------------------------------------
0  | 1   1    1    1    1    1    1    1    1    1 ...
1  | 1   1    1    1    1    1    1    1    1    1 ...
2  | 1   2    2    2    2    2    2    2    2    2 ...
3  | 1   4    5    5    5    5    5    5    5    5 ...
4  | 1   8   13   14   14   14   14   14   14   14 ...
5  | 1  16   35   41   42   42   42   42   42   42 ...
6  | 1  32   96  124  131  132  132  132  132  132 ...
7  | 1  64  267  384  420  428  429  429  429  429 ...
8  | 1 128  750 1210 1375 1420 1429 1430 1430 1430 ...
9  | 1 256 2123 3865 4576 4796 4851 4861 4862 4862 ...
...

Maple

A295679 := proc(n, k)
    if n = 0 then
        1;
    else
        add((-1)^j/n*binomial(n, j)*binomial(2*n-j*k, n+1), j=0..(n-1)/k) ;
    end if ;
end proc:
seq(seq( A295679(n, d-n), n=0..d-1), d=1..12) ; # R. J. Mathar, Oct 14 2022

Mathematica

rows = cols = 12;
col[k_] := Module[{G}, G = InverseSeries[x*(1-x)/(1-x^k) + O[x]^cols, x]; CoefficientList[1/(1 - G), x]];
A = Array[col, cols];
T[n_, k_] := A[[k, n+1]];
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 *)

Prog

(PARI)
T(n, k)=polcoeff(1/(1-serreverse(x*(1-x)/(1-x^k) + O(x^max(2, n+1)))), n);
for(n=0, 10, for(k=1, 10, print1(T(n, k), ", ")); print);

Crossrefs

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

Cf. A288942, A000108, A001453.

Sequence in context: A030424 A216656 A353435 * A287214 A287216 A145515

Adjacent sequences: A295676 A295677 A295678 * A295680 A295681 A295682

Keyword

nonn,tabl,easy

Author

Andrew Howroyd, Nov 30 2017

Status

approved