login
Sum of Gaussian binomial coefficients [ n,k ] for q=3.
(Formerly M1687)
10

%I M1687 #45 Sep 08 2022 08:44:34

%S 1,2,6,28,212,2664,56632,2052656,127902864,13721229088,2544826627424,

%T 815300788443072,452436459318538048,434188323928823259776,

%U 722197777341507864283008,2078153254879878944892861184,10366904326991986000747424911616,89478415088556766546699920236339712,1338962661056423158371347974009398601216

%N Sum of Gaussian binomial coefficients [ n,k ] for q=3.

%D J. Goldman and G.-C. Rota, The number of subspaces of a vector space, pp. 75-83 of W. T. Tutte, editor, Recent Progress in Combinatorics. Academic Press, NY, 1969.

%D I. P. Goulden and D. M. Jackson, Combinatorial Enumeration. Wiley, NY, 1983, p. 99.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

%H Vincenzo Librandi, <a href="/A006117/b006117.txt">Table of n, a(n) for n = 0..90</a>

%H R. Chapman et al., <a href="http://dx.doi.org/10.5802/jtnb.347">2-modular lattices from ternary codes</a>, J. Th. des Nombres de Bordeaux, 14 (2002), 73-85.

%H S. Hitzemann, W. Hochstattler, <a href="http://dx.doi.org/10.1016/j.disc.2010.09.001">On the combinatorics of Galois numbers</a>, Discr. Math. 310 (2010) 3551-3557, Galois Numbers G_{n}^(2).

%H Kent E. Morrison, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Morrison/morrison37.html">Integer Sequences and Matrices Over Finite Fields</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

%H M. Sved, <a href="/A006095/a006095.pdf">Gaussians and binomials</a>, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)

%F O.g.f.: A(x) = Sum_{n>=0} x^n / Product_{k=0..n} (1 - 3^k*x). - _Paul D. Hanna_, Dec 06 2007

%F a(n) = 2*a(n-1)+(3^(n-1)-1)*a(n-2), n>1. [Hitzemann and Hochstattler] - _R. J. Mathar_, Aug 21 2013

%F a(n) ~ c * 3^(n^2/4), where c = EllipticTheta[3,0,1/3] / QPochhammer[1/3,1/3] = 3.019783845699... if n is even and c = EllipticTheta[2,0,1/3]/QPochhammer[1/3,1/3] = 3.018269046371... if n is odd. - _Vaclav Kotesovec_, Aug 21 2013

%F 0 = a(n)*(2*a(n+1) + 2*a(n+2) - a(n+3)) + a(n+1)*(-6*a(n+1) + 3*a(n+2)) for all n in Z. - _Michael Somos_, Jan 25 2014

%e O.g.f.: A(x) = 1/(1-x) + x/((1-x)*(1-3x)) + x^2/((1-x)*(1-3x)*(1-9x)) + x^3/((1-x)*(1-3x)*(1-9x)*(1-27x)) + ...

%e Also generated by iterated binomial transforms in the following way:

%e [1,2,6,28,212,2664,56632,...] = BINOMIAL([1,1,3,15,129,1833,43347,..]);

%e [1,3,15,129,1833,43347,1705623,...] = BINOMIAL^2([1,1,7,67,1081,...]);

%e [1,7,67,1081,29185,1277887,...] = BINOMIAL^6([1,1,19,415,12961,...]);

%e [1,19,415,12961,684361,58352707,...] = BINOMIAL^18([1,1,55,3187,...]);

%e [1,55,3187,219673,22634209,...] = BINOMIAL^54([1,1,163,27055,4805569,...]);

%e etc.

%e G.f. = 1 + 2*x + 6*x^2 + 28*x^3 + 212*x^4 + 2664*x^5 + 56632*x^6 + 2052656*x^7 + ...

%p f:=n-> 1+ add( mul((3^(n-i)-1)/(3^(i+1)-1), i=0..k-1), k=1..n);

%t Flatten[{1,RecurrenceTable[{a[n]==2*a[n-1]+(3^(n-1)-1)*a[n-2],a[0]==1,a[1]==2},a,{n,1,15}]}] (* _Vaclav Kotesovec_, Aug 21 2013 *)

%t Table[Sum[QBinomial[n, k, 3], {k, 0, n}], {n, 0, 20}] (* _Vincenzo Librandi_, Aug 13 2016 *)

%o (PARI) a(n)=polcoeff(sum(k=0, n, x^k/prod(j=0, k, 1-3^j*x+x*O(x^n))), n) \\ _Paul D. Hanna_, Dec 06 2007

%o (Magma) [n le 2 select n else 2*Self(n-1)+(3^(n-2)-1)*Self(n-2): n in [1..40]]; // _Vincenzo Librandi_, Aug 13 2016

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_