A295679 - cp's OEIS frontend

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

Andrew Howroyd, Nov 30 2017

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

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

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.

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

Cf. A288942, A000108, A001453.

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

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

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula