

A182176


Number of affine subspaces of GF(2)^n.


8



1, 3, 11, 51, 307, 2451, 26387, 387987, 7866259, 221472147, 8703733139, 479243212179, 37070813107603, 4036214347068819, 619402703369958803, 134108807406166799763, 40994263184865380595091, 17700624176280878586721683, 10799420012335823235718509971
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

qbinomial transform of A000079 for q=2.  Vladimir Reshetnikov, Oct 17 2016
From Geoffrey Critzer, Jul 15 2017: (Start)
a(n) is the total number of vectors in all subspaces of GF(2)^n.
a(n) is the number of subspaces of GF(2)^(n+1) that do not contain a given nonzero vector. (End)


LINKS

Gaëtan Leurent, 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.


FORMULA

a(n) = Sum_{k=0..n} (2^n/2^k * Product_{i=0..k1} (2^n  2^i)/(2^k  2^i)).
G.f.: Sum_{n>=0} x^n / Product_{k=1..n+1} (12^k*x).  Paul D. Hanna, May 01 2012
a(n) ~ c * 2^((n+1)^2/4), where c = EllipticTheta[2, 0, 1/2] / QPochhammer[1/2, 1/2] = A242939 = 7.3719494907662273375414118336... if n is even, and c = EllipticTheta[3, 0, 1/2] / QPochhammer[1/2, 1/2] = A242938 = 7.3719688014613165091531912082... if n is odd.  Vaclav Kotesovec, Jun 22 2014
a(n)/[n]_q! is the coefficient of x^n in the expansion of (1 + x)*exp_q( x)*exp_q(x) when q>2 and where exp_q(x) is the q exponential function and [n]_q! is the qfactorial of n.  Geoffrey Critzer, Jul 15 2017
a(n) = (2^n  1)*A006116(n1) + A006116(n).  Geoffrey Critzer, Jul 15 2017


EXAMPLE

For n=2, there are 4 affine subspaces of dimension 0, 6 of dimension 1, and 1 of dimension 2.


MATHEMATICA

Table[Sum[2^n/2^k * Product[(2^n2^i)/(2^k2^i), {i, 0, k1}], {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Jun 22 2014 *)
Table[Sum[QBinomial[n, k, 2] 2^k, {k, 0, n}], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 17 2016 *)


PROG

(Sage) def a(n): return sum([(2^n/2^k)*prod([(2^n2^i)/(2^k2^i) for i in [0..k1]]) for k in [0..n]])
(PARI) {a(n)=polcoeff(sum(m=0, n, x^m/prod(k=1, m+1, 12^k*x+x*O(x^n))), n)} /* Paul D. Hanna, May 01 2012 */
(GAP) List([0..20], n>Sum([0..n], k>(2^n/2^k*Product([0..k1], i>(2^n2^i)/(2^k2^i))))); # Muniru A Asiru, Aug 01 2018


CROSSREFS

Cf. A006116.
Sequence in context: A056199 A230008 A007047 * A244754 A129097 A319155
Adjacent sequences: A182173 A182174 A182175 * A182177 A182178 A182179


KEYWORD

nonn,easy


AUTHOR

Gaëtan Leurent, Apr 16 2012


STATUS

approved



