|
| |
|
|
A261589
|
|
6-Modular Catalan Numbers C_{n,6}.
|
|
6
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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).
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
|
|
|
EXAMPLE
|
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.
|
|
|
MATHEMATICA
|
terms = 30; col[k_] := Module[{G}, G = InverseSeries[x*(1 - x)/(1 - x^k) + O[x]^terms, x]; CoefficientList[1/(1 - G), x]];
|
|
|
PROG
|
(PARI) Vec(1/(1-serreverse(x*(1-x)/(1-x^6) + 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(6)
|
|
|
CROSSREFS
|
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.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
