A261590 -id:A261590 - 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

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

Showing 1-5 of 5 results.

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

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

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

PARI

Sage

Formula