cp's OEIS Frontend

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

%I A261589 #27 Mar 07 2020 11:43:12
%S A261589 1,1,2,5,14,42,132,428,1420,4796,16432,56966,199444,704146,2504000,
%T A261589 8960445,32241670,116580200,423372684,1543542369,5647383786,
%U A261589 20728481590,76305607480,281648344965,1042139463066,3864822037106,14362983740692,53481776523398
%N A261589 6-Modular Catalan Numbers C_{n,6}.
%C A261589 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.
%C A261589 Theorem: C_{n,k} enumerates the following objects:
%C A261589 (1) binary trees with n internal nodes avoiding a certain subtree (i.e., comb_k^{+1}),
%C A261589 (2) plane trees with n+1 nodes whose non-root nodes have degree less than k,
%C A261589 (3) Dyck paths of length 2n avoiding a down-step followed immediately by k consecutive up-steps,
%C A261589 (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,
%C A261589 (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
%C A261589 (6) permutations of {1,2,...,n} avoiding 1-3-2 and 23...(k+1)1.
%H A261589 Andrew Howroyd, <a href="/A261589/b261589.txt">Table of n, a(n) for n = 0..200</a>
%H A261589 Nickolas Hein, Jia Huang, <a href="http://arxiv.org/abs/1508.01688">Modular Catalan Numbers</a>, arXiv:1508.01688 [math.CO], 2015-2016.
%F A261589 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).
%F A261589 G.f.: 1/(1-x*G(x)) where G(x) is g.f. of A036767. - _Andrew Howroyd_, Dec 04 2017
%F A261589 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
%e A261589 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.
%t A261589 terms = 30; col[k_] := Module[{G}, G = InverseSeries[x*(1 - x)/(1 - x^k) + O[x]^terms, x]; CoefficientList[1/(1 - G), x]];
%t A261589 col[6] (* _Jean-François Alcover_, Dec 05 2017, after _Andrew Howroyd_ *)
%o A261589 (PARI) Vec(1/(1-serreverse(x*(1-x)/(1-x^6) + O(x*x^25)))) \\ _Andrew Howroyd_, Dec 04 2017
%o A261589 (Sage)
%o A261589 def C(k):
%o A261589     print(1)
%o A261589     for n in range(1,51):
%o A261589         f = ((1-x^k)/(1-x))^n # ((x+1)^2-x^2*(x/(x+1))^(k-2))^n
%o A261589         f = f.simplify_full()
%o A261589         C = 0
%o A261589         for i in range(n):
%o A261589             C = C + (n-i)*f.coefficient(x,i)/n
%o A261589         print(C)
%o A261589 time C(6)
%Y A261589 Column k=6 of A295679.
%Y A261589 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.
%Y A261589 Cf. A036767.
%K A261589 nonn
%O A261589 0,3
%A A261589 _Nickolas Hein_, Aug 25 2015