login
5-Modular Catalan Numbers C_{n,5}.
6

%I #27 Mar 07 2020 11:43:06

%S 1,1,2,5,14,42,131,420,1375,4576,15431,52603,180957,627340,2189430,

%T 7685785,27118855,96123508,342099955,1221979374,4379357895,

%U 15742077045,56742085710,205041235750,742647580815,2695585363122,9803561513316,35720226039252,130373533268780

%N 5-Modular Catalan Numbers C_{n,5}.

%C 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 Theorem: C_{n,k} enumerates the following objects:

%C (1) binary trees with n internal nodes avoiding a certain subtree (i.e., comb_k^{+1}),

%C (2) plane trees with n+1 nodes whose non-root nodes have degree less than k,

%C (3) Dyck paths of length 2n avoiding a down-step followed immediately by k consecutive up-steps,

%C (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 (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 (6) permutations of {1,2,...,n} avoiding 1-3-2 and 23...(k+1)1.

%H Andrew Howroyd, <a href="/A261588/b261588.txt">Table of n, a(n) for n = 0..200</a>

%H Nickolas Hein and Jia Huang, <a href="http://arxiv.org/abs/1508.01688">Modular Catalan Numbers</a>, arXiv:1508.01688 [math.CO], 2015.

%H Nickolas Hein and Jia Huang, <a href="https://doi.org/10.1016/j.ejc.2016.11.004">Modular Catalan Numbers</a>, European Journal of Combinatorics 61 (2017), 197-218.

%F 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 G.f.: 1/(1-x*G(x)) where G(x) is g.f. of A036766. - _Andrew Howroyd_, Dec 04 2017

%F 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

%e 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.

%t terms = 30; col[k_] := Module[{G}, G = InverseSeries[x*(1 - x)/(1 - x^k) + O[x]^terms, x]; CoefficientList[1/(1 - G), x]];

%t col[5] (* _Jean-François Alcover_, Dec 05 2017, after _Andrew Howroyd_ *)

%o (PARI) Vec(1/(1-serreverse(x*(1-x)/(1-x^5) + O(x*x^25)))) \\ _Andrew Howroyd_, Dec 04 2017

%o (Sage)

%o def C(k):

%o print(1)

%o for n in range(1,51):

%o f = ((1-x^k)/(1-x))^n # ((x+1)^2-x^2*(x/(x+1))^(k-2))^n

%o f = f.simplify_full()

%o C = 0

%o for i in range(n):

%o C = C + (n-i)*f.coefficient(x,i)/n

%o print(C)

%o time C(5)

%o (Sage)

%o print(0,1)

%o nbound=100

%o for nMinus1 in range(nbound):

%o n=nMinus1+1

%o Cn=0

%o for lMinus1 in range(n):

%o l=lMinus1+1

%o for m5 in range(1+(n-l)/4):

%o for m4 in range(1+(n-l-4*m5)/3):

%o for m3 in range(1+(n-l-4*m5-3*m4)/2):

%o m2=n-l-4*m5-3*m4-2*m3

%o m1=n-m2-m3-m4-m5

%o Cn=Cn+l*sage.rings.arith.multinomial(m1,m2,m3,m4,m5)/n

%o print(Cn)

%Y Column k=5 of A295679.

%Y 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.

%Y Cf. A036766.

%K nonn

%O 0,3

%A _Nickolas Hein_, Aug 25 2015