A261591 8-Modular Catalan Numbers C_{n,8}.

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4861, 16784, 58695, 207452, 739840, 2658936, 9620232, 35011566, 128082523, 470731970, 1737220254, 6435115168, 23918062480, 89172805980, 333396591075, 1249717509612, 4695654554206, 17682176062376, 66720743308877

Offset

0,3

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.

Links

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

Nickolas Hein, Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2016-2016.

Formula

sum( 1<=l<=n, (l/n)sum( m_1+...+m_k=n and m_2+2m_3+...+(k-1)m_k=n-l , MC(n;m_1,...,m_k) ) ), where MC(n;m_1,...,m_k) is the multinomial coefficient associated to the multiset (m_1,...,m_k).

G.f.: 1/(1-x*G(x)) where G(x) is g.f. of A036769. - Andrew Howroyd, Dec 04 2017

Example

The Catalan number C_9=4862 counts the parenthesizations of x_1*...*x_10 where * is arbitrary. Defining * and w as above and writing x_i compactly as xi, we have x1*(x2*(x3*(x4*(x5*(x6*(x7*(x8*(x9*(x10))))))))) = x1+wx2+w^2x3+w^3x4+w^4x5+w^5x6+w^6x7+w^7x8+x9+wx10 = x1*(x2*(x3*(x4*(x5*(x6*(x7*(x8*(x9))))))))*(x10). For n=9 and k=8, these are the only parenthesizations that give the same value for x1*...*x10, so C_{9,8}=4862-1=4861.

Mathematica

terms = 30; col[k_] := Module[{G}, G = InverseSeries[x*(1 - x)/(1 - x^k) + O[x]^terms, x]; CoefficientList[1/(1 - G), x]];
col[8] (* Jean-François Alcover, Dec 05 2017, after Andrew Howroyd *)

Prog

(PARI) Vec(1/(1-serreverse(x*(1-x)/(1-x^8) + O(x*x^25)))) \\ Andrew Howroyd, Dec 04 2017
(Sage)
def C(k):
    print(1)
    for n in range(1, 51):
        f = ((1-x^k)/(1-x))^n # ((x+1)^2-x^2*(x/(x+1))^(k-2))^n
        f = f.simplify_full()
        C = 0
        for i in range(n):
            C = C + (n-i)*f.coefficient(x, i)/n
        print(C)
time C(8)

Crossrefs

Column k=8 of A295679.

C_{n,1} is the all 1's sequence A000012. For C_{n,k} with k=2,3,4 see A011782, A005773, A159772. For k=5,6,7,9 see A261588, A261589, A261590, A261592.

Cf. A036769.

Sequence in context: A036769 A287971 A033191 * A291823 A287972 A243838

Adjacent sequences: A261588 A261589 A261590 * A261592 A261593 A261594

Keyword

nonn

Author

Nickolas Hein, Aug 25 2015

Status

approved