A006118 Sum of Gaussian binomial coefficients [ n,k ] for q=4.

1, 2, 7, 44, 529, 12278, 565723, 51409856, 9371059621, 3387887032202, 2463333456292207, 3557380311703796564, 10339081666350180289849, 59703612489554311631068958

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

References

• 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.
• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration. Wiley, NY, 1983, p. 99.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..80
• S. Hitzemann, W. Hochstattler, On the combinatorics of Galois numbers, Discr. Math. 310 (2010) 3551-3557.
• Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.
• M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)

Crossrefs

Row sums of triangle A022168.

Programs

Magma

[n le 2 select n else 2*Self(n-1)+(4^(n-2)-1)*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Aug 13 2016

Mathematica

Flatten[{1,RecurrenceTable[{a[n]==2*a[n-1]+(4^(n-1)-1)*a[n-2],a[0]==1,a[1]==2},a,{n,1,15}]}] (* Vaclav Kotesovec, Aug 21 2013 *)
Table[Sum[QBinomial[n, k, 4], {k, 0, n}], {n, 0, 20}] (* Vincenzo Librandi, Aug 13 2016 *)

Formula

a(n) = 2*a(n-1)+(4^(n-1)-1)*a(n-2), n>1. [Hitzemann and Hochstattler]. - R. J. Mathar, Aug 21 2013

a(n) ~ c * 4^(n^2/4), where c = EllipticTheta[3,0,1/4]/QPochhammer[1/4,1/4] = 2.189888057761... if n is even and c = EllipticTheta[2,0,1/4]/QPochhammer[1/4,1/4] = 2.182810929357... if n is odd. - Vaclav Kotesovec, Aug 21 2013