cp's OEIS Frontend

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

%I A261590 #27 Mar 07 2020 11:43:16
%S A261590 1,1,2,5,14,42,132,429,1429,4851,16718,58331,205632,731272,2620176,
%T A261590 9449695,34276230,124959485,457621780,1682686509,6209928010,
%U A261590 22993696620,85396852670,318034472365,1187429860461,4443824658798,16666506959312,62632954529054
%N A261590 7-Modular Catalan Numbers C_{n,7}.
%C A261590 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 A261590 Theorem: C_{n,k} enumerates the following objects:
%C A261590 (1) binary trees with n internal nodes avoiding a certain subtree (i.e., comb_k^{+1}),
%C A261590 (2) plane trees with n+1 nodes whose non-root nodes have degree less than k,
%C A261590 (3) Dyck paths of length 2n avoiding a down-step followed immediately by k consecutive up-steps,
%C A261590 (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 A261590 (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 A261590 (6) permutations of {1,2,...,n} avoiding 1-3-2 and 23...(k+1)1.
%H A261590 Andrew Howroyd, <a href="/A261590/b261590.txt">Table of n, a(n) for n = 0..200</a>
%H A261590 Nickolas Hein, Jia Huang, <a href="http://arxiv.org/abs/1508.01688">Modular Catalan Numbers</a>, arXiv:1508.01688 [math.CO], 2015-2016.
%H A261590 Vaclav Kotesovec, <a href="/A261590/a261590.txt">Recurrence (of order 7)</a>
%F A261590 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 A261590 G.f.: 1/(1-x*G(x)) where G(x) is g.f. of A036768. - _Andrew Howroyd_, Dec 04 2017
%e A261590 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.
%t A261590 terms = 30; col[k_] := Module[{G}, G = InverseSeries[x*(1 - x)/(1 - x^k) + O[x]^terms, x]; CoefficientList[1/(1 - G), x]];
%t A261590 col[7] (* _Jean-François Alcover_, Dec 05 2017, after _Andrew Howroyd_ *)
%o A261590 (PARI) Vec(1/(1-serreverse(x*(1-x)/(1-x^7) + O(x*x^25)))) \\ _Andrew Howroyd_, Dec 04 2017
%o A261590 (Sage)
%o A261590 def C(k):
%o A261590     print(1)
%o A261590     for n in range(1,51):
%o A261590         f = ((1-x^k)/(1-x))^n # ((x+1)^2-x^2*(x/(x+1))^(k-2))^n
%o A261590         f = f.simplify_full()
%o A261590         C = 0
%o A261590         for i in range(n):
%o A261590             C = C + (n-i)*f.coefficient(x,i)/n
%o A261590         print(C)
%o A261590 time C(7)
%Y A261590 Column k=7 of A295679.
%Y A261590 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.
%Y A261590 Cf. A036768.
%K A261590 nonn
%O A261590 0,3
%A A261590 _Nickolas Hein_, Aug 25 2015