login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A295679 Array read by antidiagonals: T(n,k) = k-Modular Catalan numbers C_{n,k} (n >= 0, k > 0). 8
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 (list; table; graph; refs; listen; history; text; internal format)
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 ...

...

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: A134132 A030424 A216656 * A287214 A287216 A145515

Adjacent sequences:  A295676 A295677 A295678 * A295680 A295681 A295682

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Nov 30 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 11:10 EDT 2018. Contains 316414 sequences. (Running on oeis4.)