A006116 Sum of Gaussian binomial coefficients [n,k] for q=2 and k=0..n. (Formerly M1501)

1, 2, 5, 16, 67, 374, 2825, 29212, 417199, 8283458, 229755605, 8933488744, 488176700923, 37558989808526, 4073773336877345, 623476476706836148, 134732283882873635911, 41128995468748254231002, 17741753171749626840952685, 10817161765507572862559462656

Offset

0,2

Comments

Also number of distinct binary linear codes of length n and any dimension.

Equivalently, number of subgroups of the Abelian group (C_2)^n.

Let V_n be an n-dimensional vector space over a field with 2 elements. Let P(V_n) be the collection of all subspaces of V_n. Then a(n-1) is the number of times any given nonzero vector of V_n appears in P(V_n). - Geoffrey Critzer, Jun 05 2017

With V_n and P(V_n) as above, a(n) is also the cardinality of P(V_n). - Vaia Patta, Jun 25 2019

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.

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 698.

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

Alois P. Heinz, Table of n, a(n) for n = 0..100

Geoffrey Critzer, Combinatorics of Vector Spaces over Finite Fields, Master's thesis, Emporia State University, 2018.

S. Hitzemann and W. Hochstattler, On the combinatorics of Galois numbers, Discr. Math. 310 (2010) 3551-3557, Galois Numbers G_{n}^(2).

Hsien-Kuei Hwang, Emma Yu Jin, and Michael J. Schlosser, Asymptotics and statistics on Fishburn Matrices: dimension distribution and a conjecture of Stoimenow, arXiv:2012.13570 [math.CO], 2020.

Vjekoslav Kovač and Hrvoje Šikić, Characterizations of democratic systems of translates on locally compact abelian groups, arXiv:1709.01747 [math.FA], 2017.

Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

D. Slepian, A class of binary signaling alphabets, Bell System Tech. J. 35 (1956), 203-234.

D. Slepian, Some further theory of group codes, Bell System Tech. J. 39 1960 1219-1252.

M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)

Index entries for sequences related to binary linear codes

Formula

O.g.f.: A(x) = Sum_{n>=0} x^n / Product_{k=0..n} (1 - 2^k*x). - Paul D. Hanna, Dec 06 2007

From Paul D. Hanna, Nov 29 2008: (Start)

Coefficients of the square of the q-exponential of x evaluated at q=2, where the q-exponential of x = Sum_{n>=0} x^n/F(n) and F(n) = Product{i=1..n} (q^i-1)/(q-1) is the q-factorial of n.

G.f.: (Sum_{k=0..n} x^n/F(n))^2 = Sum_{k=0..n} a(n)*x^n/F(n) where F(n) = A005329(n) = Product{i=1..n} (2^i - 1).

a(n) = Sum_{k=0..n} F(n)/(F(k)*F(n-k)) where F(n)=A005329(n) is the 2-factorial of n.

a(n) = Sum_{k=0..n} Product_{i=1..n-k} (2^(i+k) - 1)/(2^i - 1).

a(n) = Sum_{k=0..A033638(n)} A083906(n,k)*2^k. (End)

G.f.: 1 + x*(G(0) - 1)/(x-1) where G(k) = 1 - 1/(1-2^k*x)/(1-x/(x-1/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 16 2013

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

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

Example

O.g.f.: A(x) = 1/(1-x) + x/((1-x)*(1-2x)) + x^2/((1-x)*(1-2x)*(1-4x)) + x^3/((1-x)*(1-2x)*(1-4x)*(1-8x)) + ...
Also generated by iterated binomial transforms in the following way:
[1,2,5,16,67,374,2825,29212,...] = BINOMIAL([1,1,2,6,26,158,1330,...]); see A135922;
[1,2,6,26,158,1330,15414,245578,...] = BINOMIAL([1,1,3,13,83,749,...]);
[1,3,13,83,749,9363,160877,...] = BINOMIAL^2([1,1,5,33,317,4361,...]);
[1,5,33,317,4361,82789,2148561,...] = BINOMIAL^4([1,1,9,97,1433,...]);
[1,9,97,1433,30545,902601,...] = BINOMIAL^8([1,1,17,321,7601,252833,...]);
etc.

Maple

gf:= m-> add(x^n/mul(1-2^k*x, k=0..n), n=0..m):
a:= n-> coeff(series(gf(n), x, n+1), x, n):
seq(a(n), n=0..20);  # Alois P. Heinz, Apr 24 2012
# second Maple program:
b:= proc(n, m) option remember; `if`(n=0, 1,
      2^m*b(n-1, m)+b(n-1, m+1))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 08 2021

Mathematica

faq[n_, q_] = Product[(1-q^(1+k))/(1-q), {k, 0, n-1}]; qbin[n_, m_, q_] = faq[n, q]/(faq[m, q]*faq[n-m, q]); a[n_] := Sum[qbin[n, k, 2], {k, 0, n}]; a /@ Range[0, 19] (* Jean-François Alcover, Jul 21 2011 *)
Flatten[{1, RecurrenceTable[{a[n]==2*a[n-1]+(2^(n-1)-1)*a[n-2], a[0]==1, a[1]==2}, a, {n, 1, 15}]}] (* Vaclav Kotesovec, Aug 21 2013 *)
QP = QPochhammer; a[n_] := Sum[QP[2, 2, n]/(QP[2, 2, k]*QP[2, 2, n-k]), {k, 0, n}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Nov 23 2015 *)
Table[Sum[QBinomial[n, k, 2], {k, 0, n}], {n, 0, 19}] (* Ivan Neretin, Mar 28 2016 *)

Prog

(PARI) a(n)=polcoeff(sum(k=0, n, x^k/prod(j=0, k, 1-2^j*x+x*O(x^n))), n) \\ Paul D. Hanna, Dec 06 2007
(PARI) a(n, q=2)=sum(k=0, n, prod(i=1, n-k, (q^(i+k)-1)/(q^i-1))) \\ Paul D. Hanna, Nov 29 2008
(Magma) I:=[1, 2]; [n le 2 select I[n] else 2*Self(n-1)+(2^(n-2)-1)*Self(n-2): n in [1..20]]; // Vincenzo Librandi, Aug 12 2014

Crossrefs

Cf. A006516. Row sums of A022166.

Cf. A005329, A083906. - Paul D. Hanna, Nov 29 2008

Sequence in context: A275518 A005163 A359986 * A122082 A002631 A107948

Adjacent sequences: A006113 A006114 A006115 * A006117 A006118 A006119

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Status

approved