A159772 -id:A159772 - cp's OEIS frontend

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

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

A261588 5-Modular Catalan Numbers C_{n,5}.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 131, 420, 1375, 4576, 15431, 52603, 180957, 627340, 2189430, 7685785, 27118855, 96123508, 342099955, 1221979374, 4379357895, 15742077045, 56742085710, 205041235750, 742647580815, 2695585363122, 9803561513316, 35720226039252, 130373533268780

Offset: 0

Nickolas Hein, Aug 25 2015

nonn

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.

			The Catalan number C_6=132 counts the parenthesizations of x_1*...*x_7 where * is arbitrary. Defining * and w as above and writing x_i compactly as xi, we have x1*(x2*(x3*(x4*(x5*(x6*(x7)))))) = x1+wx2+w^2x3+w^3x4+w^4x5+x6+wx7 = x1*(x2*(x3*(x4*(x5*(x6)))))*(x7). For n=6 and k=5, these are the only parenthesizations that give the same value for x1*...*x7, so C_{6,5}=132-1=131.

Andrew Howroyd, Table of n, a(n) for n = 0..200
Nickolas Hein and Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015.
Nickolas Hein and Jia Huang, Modular Catalan Numbers, European Journal of Combinatorics 61 (2017), 197-218.

Column k=5 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=6,7,8,9 see A261589, A261590, A261591, A261592.
Cf. A036766.

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

Vec(1/(1-serreverse(x*(1-x)/(1-x^5) + O(x*x^25)))) \\ Andrew Howroyd, Dec 04 2017

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

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 A036766. - Andrew Howroyd, Dec 04 2017
Recurrence: 3*n*(3*n - 2)*(3*n - 1)*(1309*n^5 - 14388*n^4 + 60934*n^3 - 124236*n^2 + 121825*n - 45948)*a(n) = (299761*n^8 - 3779182*n^7 + 19492177*n^6 - 53378731*n^5 + 84116656*n^4 - 77081911*n^3 + 39268230*n^2 - 9775512*n + 829440)*a(n-1) - 5*(119119*n^8 - 1601215*n^7 + 8920729*n^6 - 26755339*n^5 + 46820344*n^4 - 48217102*n^3 + 27785664*n^2 - 7773768*n + 712800)*a(n-2) - 25*(n-3)*(1309*n^7 - 11770*n^6 + 38824*n^5 - 62344*n^4 + 74887*n^3 - 107794*n^2 + 101952*n - 33120)*a(n-3) - 125*(n-4)*(n-3)*(1309*n^6 - 10461*n^5 + 28528*n^4 - 30261*n^3 + 7999*n^2 + 3390*n - 1080)*a(n-4) - 625*(n-5)*(n-4)*(n-3)*(1309*n^5 - 7843*n^4 + 16472*n^3 - 14672*n^2 + 5148*n - 504)*a(n-5). - Vaclav Kotesovec, Dec 05 2017

A261589 6-Modular Catalan Numbers C_{n,6}.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 428, 1420, 4796, 16432, 56966, 199444, 704146, 2504000, 8960445, 32241670, 116580200, 423372684, 1543542369, 5647383786, 20728481590, 76305607480, 281648344965, 1042139463066, 3864822037106, 14362983740692, 53481776523398

Offset: 0

Nickolas Hein, Aug 25 2015

nonn

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.

			The Catalan number C_7=429 counts the parenthesizations of x_1*...*x_8 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))))))) = x1+wx2+w^2x3+w^3x4+w^4x5+w^5x6+x7+wx8 = x1*(x2*(x3*(x4*(x5*(x6*(x7))))))*(x8). For n=7 and k=6, these are the only parenthesizations that give the same value for x1*...*x8, so C_{7,6}=429-1=428.

Andrew Howroyd, Table of n, a(n) for n = 0..200
Nickolas Hein, Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015-2016.

Column k=6 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,7,8,9 see A261588, A261590, A261591, A261592.
Cf. A036767.

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

Vec(1/(1-serreverse(x*(1-x)/(1-x^6) + O(x*x^25)))) \\ Andrew Howroyd, Dec 04 2017

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

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 A036767. - Andrew Howroyd, Dec 04 2017
Recurrence: 8*n*(2*n - 1)*(4*n - 3)*(4*n - 1)*(10916887*n^9 - 249224042*n^8 + 2469255538*n^7 - 13933215932*n^6 + 49334513763*n^5 - 113647334214*n^4 + 170286019860*n^3 - 160004333492*n^2 + 85539013792*n - 19822693440)*a(n) = 3*(9508608577*n^13 - 237215797097*n^12 + 2623858643982*n^11 - 16999631384890*n^10 + 71778494499061*n^9 - 207873203457553*n^8 + 423002845054480*n^7 - 609054955793764*n^6 + 616019881995932*n^5 - 427963644130760*n^4 + 195602628794128*n^3 - 54415561156256*n^2 + 7923069832320*n - 416553984000)*a(n-1) - 6*(12412500519*n^13 - 321587757141*n^12 + 3711217654502*n^11 - 25208616228279*n^10 + 112156507241451*n^9 - 344001598358364*n^8 + 745080116604760*n^7 - 1147205777244243*n^6 + 1245874269527820*n^5 - 932293147229545*n^4 + 459871406685588*n^3 - 138195004254428*n^2 + 21782980665360*n - 1261019808000)*a(n-2) + 36*(n-3)*(687763881*n^12 - 16781886459*n^11 + 179899148857*n^10 - 1116006568486*n^9 + 4439364432038*n^8 - 11848465605195*n^7 + 21556040876457*n^6 - 26592812193824*n^5 + 21678236082931*n^4 - 11083403407596*n^3 + 3237388989236*n^2 - 458954256240*n + 24454886400)*a(n-3) - 216*(n-4)*(n-3)*(10916887*n^11 - 205556494*n^10 + 1637060823*n^9 - 7312163106*n^8 + 20993566701*n^7 - 44229711078*n^6 + 78086672677*n^5 - 116636175274*n^4 + 128035289512*n^3 - 87494286088*n^2 + 31392748560*n - 4319092800)*a(n-4) - 1296*(n-5)*(n-4)*(n-3)*(10916887*n^10 - 183722720*n^9 + 1276350867*n^8 - 4759019384*n^7 + 10358683545*n^6 - 13414621556*n^5 + 10161953673*n^4 - 4442494876*n^3 + 1316475548*n^2 - 382696304*n + 67140480)*a(n-5) - 7776*(n-6)*(n-5)*(n-4)*(n-3)*(10916887*n^9 - 150972059*n^8 + 868471134*n^7 - 2709681834*n^6 + 5008565879*n^5 - 5619215727*n^4 + 3761917980*n^3 - 1414279492*n^2 + 261591168*n - 17081280)*a(n-6). - Vaclav Kotesovec, Dec 05 2017

A261590 7-Modular Catalan Numbers C_{n,7}.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1429, 4851, 16718, 58331, 205632, 731272, 2620176, 9449695, 34276230, 124959485, 457621780, 1682686509, 6209928010, 22993696620, 85396852670, 318034472365, 1187429860461, 4443824658798, 16666506959312, 62632954529054

Offset: 0

Nickolas Hein, Aug 25 2015

nonn

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.

			The Catalan number C_8=1430 counts the parenthesizations of x_1*...*x_9 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)))))))) = x1+wx2+w^2x3+w^3x4+w^4x5+w^5x6+w^6x7+x8+wx9 = x1*(x2*(x3*(x4*(x5*(x6*(x7*(x8)))))))*(x9). For n=8 and k=7, these are the only parenthesizations that give the same value for x1*...*x9, so C_{8,7}=1430-1=1429.

Andrew Howroyd, Table of n, a(n) for n = 0..200
Nickolas Hein, Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015-2016.
Vaclav Kotesovec, Recurrence (of order 7)

Column k=7 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,8,9 see A261588, A261589, A261591, A261592.
Cf. A036768.

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

Vec(1/(1-serreverse(x*(1-x)/(1-x^7) + O(x*x^25)))) \\ Andrew Howroyd, Dec 04 2017

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

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 A036768. - Andrew Howroyd, Dec 04 2017

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

Original entry on oeis.org

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

Nickolas Hein, Aug 25 2015

nonn

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.

			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.

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.

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.

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

Vec(1/(1-serreverse(x*(1-x)/(1-x^8) + O(x*x^25)))) \\ Andrew Howroyd, Dec 04 2017

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)

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

A261592 9-Modular Catalan Numbers C_{n,9}.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16795, 58773, 207907, 742220, 2670564, 9674496, 35256723, 129164090, 475418625, 1757248194, 6519768464, 24272733060, 90648139140, 339497371575, 1274821281747, 4798525000860, 18102238168134, 68430875696534

Offset: 0

Nickolas Hein, Aug 25 2015

nonn

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.

			The Catalan number C_10=16796 counts the parenthesizations of x_1*...*x_11 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*(x11)))))))))) = x1+wx2+w^2x3+w^3x4+w^4x5+w^5x6+w^6x7+w^7x8+w^8x9+x10+wx11 = x1*(x2*(x3*(x4*(x5*(x6*(x7*(x8*(x9*(x10)))))))))*(x11). For n=10 and k=9, these are the only parenthesizations that give the same value for x1*...*x11, so C_{10,9}=16796-1=16795.

Andrew Howroyd, Table of n, a(n) for n = 0..200
Nickolas Hein, Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015-2016.

Column k=9 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,8 see A261588, A261589, A261590, A261591.
Cf. A291823.

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

Vec(1/(1-serreverse(x*(1-x)/(1-x^9) + O(x*x^25)))) \\ Andrew Howroyd, Nov 29 2017

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

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 A291823. - Andrew Howroyd, Nov 29 2017

A064580 Triangle associated with rooted trees with a degree constraint (A036765).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 5, 5, 1, 4, 9, 14, 13, 1, 5, 14, 28, 40, 36, 1, 6, 20, 48, 87, 118, 104, 1, 7, 27, 75, 161, 273, 357, 309, 1, 8, 35, 110, 270, 536, 866, 1100, 939, 1, 9, 44, 154, 423, 951, 1782, 2772, 3441, 2905, 1, 10, 54, 208, 630, 1572, 3310, 5928, 8946, 10900, 9118

Offset: 0

Henry Bottomley, Sep 21 2001

Main diagonal is A036765. - Paul D. Hanna, Nov 18 2016

			Triangle begins:
  1;
  1,  1;
  1,  2,  2;
  1,  3,  5,  5;
  1,  4,  9, 14, 13;
  1,  5, 14, 28, 40, 36;
  ...

Columns include A000012, A000027, A000096.
Main diagonal is A036765.
The sequence of triangles A010054 (triangle indicator), A007318 (Pascal), A026300 (Motzkin), A064580, ... converges to the triangle A009766 (Catalan).
Row sums give A159772.

a[n_, k_] /; 0 <= k <= n = a[n, k] = a[n - 1, k] + a[n - 1, k - 1] + a[n - 1, k - 2] + a[n - 1, k - 3]; a[0, 0] = 1; a[, ] = 0;
Table[a[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 30 2018 *)

# uses[riordan_array from A256893]
M = riordan_array(1, x/(1+x+x^2+x^3), 12).inverse()
for m in M[1:]:
    print([r for r in reversed(list(m)) if r != 0]) # Peter Luschny, Aug 17 2016

a(n, k) = a(n-1, k) + a(n-1, k-1) + a(n-1, k-2) + a(n-1, k-3) with a(0, 0)=1 and a(n, k)=0 if n < k or k < 0.

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 17 2007

A161746 The number of equivalence classes of n-leaf binary trees with respect to contiguous pattern avoidance.

Original entry on oeis.org

1, 1, 1, 2, 3, 7, 15, 43, 136

Offset: 1

Eric Rowland, Jun 17 2009

			Representatives of the a(6) = 7 equivalence classes of 6-leaf binary trees are given in A036766, A159768, A159769, A159770, A159771, A159772, and A159773.

Andrey T. Cherkasov and Dmitri Piontkovski, Wilf classes of non-symmetric operads, arXiv:2105.08880 [math.CO], 2021.
L. Pudwell, Pattern avoidance in trees, (slides from a talk, mentions many sequences), 2012. - _N. J. A. Sloane_, Jan 03 2013
Eric S. Rowland, Pattern avoidance in binary trees, arXiv:0809.0488 [math.CO], 2008-2010.
Eric S. Rowland, Pattern avoidance in binary trees, J. Comb. Theory A 117 (6) (2010) 741-758.

Cf. A099952.

Per Cherkasov and Piontkovski, a(8) corrected by Eric Rowland, May 22 2021

a(9) from Eric Rowland, Apr 25 2024

Showing 1-9 of 9 results.

cp's OEIS Frontend

A161898 Incorrect version of A159772.

Views

Author

Keywords

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

A261588 5-Modular Catalan Numbers C_{n,5}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A261589 6-Modular Catalan Numbers C_{n,6}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A261590 7-Modular Catalan Numbers C_{n,7}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A261592 9-Modular Catalan Numbers C_{n,9}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica