|
%I M1501 #105 Sep 08 2022 08:44:34
%S 1,2,5,16,67,374,2825,29212,417199,8283458,229755605,8933488744,
%T 488176700923,37558989808526,4073773336877345,623476476706836148,
%U 134732283882873635911,41128995468748254231002,17741753171749626840952685,10817161765507572862559462656
%N Sum of Gaussian binomial coefficients [n,k] for q=2 and k=0..n.
%C Also number of distinct binary linear codes of length n and any dimension.
%C Equivalently, number of subgroups of the Abelian group (C_2)^n.
%C 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
%C With V_n and P(V_n) as above, a(n) is also the cardinality of P(V_n). - _Vaia Patta_, Jun 25 2019
%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 F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 698.
%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 Alois P. Heinz, <a href="/A006116/b006116.txt">Table of n, a(n) for n = 0..100</a>
%H Geoffrey Critzer, <a href="https://esirc.emporia.edu/handle/123456789/3595">Combinatorics of Vector Spaces over Finite Fields</a>, Master's thesis, Emporia State University, 2018.
%H S. Hitzemann and 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 Hsien-Kuei Hwang, Emma Yu Jin, and Michael J. Schlosser, <a href="https://arxiv.org/abs/2012.13570">Asymptotics and statistics on Fishburn Matrices: dimension distribution and a conjecture of Stoimenow</a>, arXiv:2012.13570 [math.CO], 2020.
%H Vjekoslav Kovač and Hrvoje Šikić, <a href="https://arxiv.org/abs/1709.01747">Characterizations of democratic systems of translates on locally compact abelian groups</a>, arXiv:1709.01747 [math.FA], 2017.
%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 D. Slepian, <a href="https://archive.org/details/bstj35-1-203">A class of binary signaling alphabets</a>, Bell System Tech. J. 35 (1956), 203-234.
%H D. Slepian, <a href="https://archive.org/details/bstj39-5-1219">Some further theory of group codes</a>, Bell System Tech. J. 39 1960 1219-1252.
%H M. Sved, <a href="/A006095/a006095.pdf">Gaussians and binomials</a>, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)
%H <a href="/index/Coa#codes_binary_linear">Index entries for sequences related to binary linear codes</a>
%F O.g.f.: A(x) = Sum_{n>=0} x^n / Product_{k=0..n} (1 - 2^k*x). - _Paul D. Hanna_, Dec 06 2007
%F From _Paul D. Hanna_, Nov 29 2008: (Start)
%F 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.
%F 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).
%F a(n) = Sum_{k=0..n} F(n)/(F(k)*F(n-k)) where F(n)=A005329(n) is the 2-factorial of n.
%F a(n) = Sum_{k=0..n} Product_{i=1..n-k} (2^(i+k) - 1)/(2^i - 1).
%F a(n) = Sum_{k=0..A033638(n)} A083906(n,k)*2^k. (End)
%F 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
%F a(n) = 2*a(n-1) + (2^(n-1)-1)*a(n-2). [Hitzemann and Hochstattler]. - _R. J. Mathar_, Aug 21 2013
%F 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
%e 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)) + ...
%e Also generated by iterated binomial transforms in the following way:
%e [1,2,5,16,67,374,2825,29212,...] = BINOMIAL([1,1,2,6,26,158,1330,...]); see A135922;
%e [1,2,6,26,158,1330,15414,245578,...] = BINOMIAL([1,1,3,13,83,749,...]);
%e [1,3,13,83,749,9363,160877,...] = BINOMIAL^2([1,1,5,33,317,4361,...]);
%e [1,5,33,317,4361,82789,2148561,...] = BINOMIAL^4([1,1,9,97,1433,...]);
%e [1,9,97,1433,30545,902601,...] = BINOMIAL^8([1,1,17,321,7601,252833,...]);
%e etc.
%p gf:= m-> add(x^n/mul(1-2^k*x, k=0..n), n=0..m):
%p a:= n-> coeff(series(gf(n), x, n+1), x, n):
%p seq(a(n), n=0..20); # _Alois P. Heinz_, Apr 24 2012
%p # second Maple program:
%p b:= proc(n, m) option remember; `if`(n=0, 1,
%p 2^m*b(n-1, m)+b(n-1, m+1))
%p end:
%p a:= n-> b(n, 0):
%p seq(a(n), n=0..25); # _Alois P. Heinz_, Aug 08 2021
%t 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 *)
%t 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 *)
%t 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 *)
%t Table[Sum[QBinomial[n, k, 2], {k, 0, n}], {n, 0, 19}] (* _Ivan Neretin_, Mar 28 2016 *)
%o (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
%o (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
%o (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
%Y Cf. A006516. Row sums of A022166.
%Y Cf. A005329, A083906. - _Paul D. Hanna_, Nov 29 2008
%K nonn,easy,nice
%O 0,2
%A _N. J. A. Sloane_
|
