A006116 -id:A006116 - cp's OEIS frontend

A135922 Inverse binomial transform of A006116, which is the sum of Gaussian binomial coefficients [n,k] for q=2.

1, 1, 2, 6, 26, 158, 1330, 15414, 245578, 5382862, 162700898, 6801417318, 394502066810, 31849226170622, 3589334331706258, 566102993389615254, 125225331231990004138, 38920655753545108286254, 17021548688670112527781058, 10486973328106497739526535366

Offset: 0

Paul D. Hanna, Dec 06 2007

nonn

Let B = {v_1,v_2,...,v_n} be a basis for F_2^n.  a(n) is the number of subspaces of F_2^n that do not contain any of the vectors in B.  Moreover, for 1<=k<=n, let S be a size k subset of B. a(k) is the number of subspaces of F_2^n that do not contain any of the vectors in S but do contain all the vectors in B - S. - Geoffrey Critzer, May 03 2025
Also number of Stanley graphs on n nodes. For precise definition see Knuth (1997). - Alois P. Heinz, Sep 24 2019
Also the number of naturally labeled posets on [n] with height at most two. - David Bevan, Jul 28 2022; Nov 16 2023
Also the number of sign mappings X:([n] choose 2) -> {+,-} such that for any ordered 3-tuple aManfred Scheucher, Jan 05 2024

			O.g.f.: A(x) = 1 + x/(1-x) + x^2/((1-x)*(1-3x)) + x^3/((1-x)*(1-3x)*(1-7x)) + x^4/((1-x)*(1-3x)*(1-7x)*(1-15x)) + ...

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 318.

Alois P. Heinz, Table of n, a(n) for n = 0..115
David Bevan, Gi-Sang Cheon and Sergey Kitaev, On naturally labelled posets and permutations avoiding 12-34, arXiv:2311.08023 [math.CO], 2023.
Lucas Gagnon, The combinatorics of normal subgroups in the unipotent upper triangular group, arXiv:2012.00108 [math.CO], 2020.
D. E. Knuth, Letter to Daniel Ullman and others, Apr 29 1997 [Annotated scanned copy, with permission]
Zvi Rosen and Yan X. Zhang, Convex Neural Codes in Dimension 1, arXiv:1702.06907 [math.CO], 2017. Mentions this sequence.
R. P. Stanley, Problem 10572, The American Mathematical Monthly, 104(2) (1997), 168.
R. P. Stanley and S. C. Locke, Graphs without increasing paths: Solution to Problem 10572, The American Mathematical Monthly, 106(2) (1999), 168.

Cf. A006116, A323841, A323842, A323843, A139382, A006455, A356111.

b:= proc(n) option remember; add(mul(
      (2^(i+k)-1)/(2^i-1), i=1..n-k), k=0..n)
    end:
a:= proc(n) option remember;
      add(b(n-j)*binomial(n,j)*(-1)^j, j=0..n)
    end:
seq(a(n), n=0..19);  # Alois P. Heinz, Sep 24 2019

Table[SeriesCoefficient[Sum[x^n/Product[(1-(2^k-1)*x),{k,0,n}],{n,0,nn}],{x,0,nn}] ,{nn,0,20}] (* Vaclav Kotesovec, Aug 23 2013 *)
b[n_] := b[n] = Sum[Product[(2^(i+k)-1)/(2^i-1), {i, 1, n-k}], {k, 0, n}];
a[n_] := a[n] = Sum[(-1)^j b[n-j] Binomial[n, j], {j, 0, n}];
a /@ Range[0, 19] (* Jean-François Alcover, Mar 10 2020, after Alois P. Heinz *)

a(n)=polcoeff(sum(k=0, n, x^k/prod(j=0, k, 1-(2^j-1)*x+x*O(x^n))), n)

# After Vladimir Kruchinin.
def a(n):
    @cached_function
    def T(n, k):
        if k == 1 or k == n: return 1
        return (2^k-1)*T(n-1, k) + T(n-1, k-1)
    return sum(T(n, k) for k in (1..n)) if n > 0 else 1
print([a(n) for n in (0..19)]) # Peter Luschny, Feb 26 2020

O.g.f.: A(x) = Sum_{n>=0} x^n / Product_{k=0..n} (1 - (2^k-1)*x).
G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - 1/(1-x*(2^k-1))/(1-x/(x-1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jan 16 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 23 2013
a(n) = Sum_{k=0..n} qStirling2(n,k), where qStirling2 is the triangle A139382. - Vladimir Kruchinin, Feb 26 2020
G.f.: f(1), where f(y) = 1 + x*((y-1)*f(y) + f(2*y)). - David Bevan, Jul 28 2022
E.g.f.:  exp(-x)*g(x) where g(x) is the e.g.f. for A006116. (given in D. E. Knuth link) - Geoffrey Critzer, May 03 2025

References for Stanley graphs added by David Bevan, Jul 24 2024

A227961 Triangle T(n,k) read by rows: how often does k appear among the first A006116(n) entries of A198260?

Original entry on oeis.org

2, 3, 2, 4, 8, 2, 2, 5, 22, 8, 24, 2, 2, 2, 2, 6, 52, 22, 150, 8, 24, 24, 72, 2, 2, 2, 2, 2, 2, 2, 2, 7, 114, 52, 740, 22, 150, 150, 1046, 8, 24, 24, 72, 24, 72, 72, 216, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 8, 240, 114, 3282, 52, 740

Offset: 1

Tilman Piesk, Aug 01 2013

T(n,k) shows how often k appears among the first A006116(n) entries of A198260.
n and k are counted from 1:
2,
3,  2,
4,  8, 2,  2,
5, 22, 8, 24, 2,  2,  2,   2,
6, 52,22,150, 8, 24, 24,  72,2, 2, 2, 2, 2, 2, 2,  2,
7,114,52,740,22,150,150,1046,8,24,24,72,24,72,72,216,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2
The number of different entries per row is 1,2,3,5,8,12,16...
The second column 2,8,22,52,114,240... seems to appear in other columns as well.
Row lengths are powers of two (A000079).
Row sums are the sums of Gaussian binomial coefficients (A006116).

Tilman Piesk, First 7 rows of triangle, flattened
Tilman Piesk, First 7 rows of triangle

A022166 Triangle of Gaussian binomial coefficients (or q-binomial coefficients) [n,k] for q = 2.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 7, 1, 1, 15, 35, 15, 1, 1, 31, 155, 155, 31, 1, 1, 63, 651, 1395, 651, 63, 1, 1, 127, 2667, 11811, 11811, 2667, 127, 1, 1, 255, 10795, 97155, 200787, 97155, 10795, 255, 1, 1, 511, 43435, 788035, 3309747, 3309747, 788035, 43435, 511, 1

Offset: 0

N. J. A. Sloane

Also number of distinct binary linear [n,k] codes.
Row sums give A006116.
Central terms are A006098.
T(n,k) is the number of subgroups of the Abelian group (C_2)^n that have order 2^k. - Geoffrey Critzer, Mar 28 2016
T(n,k) is the number of k-subspaces of the finite vector space GF(2)^n. - Jianing Song, Jan 31 2020

			Triangle begins:
  1;
  1,   1;
  1,   3,    1;
  1,   7,    7,     1;
  1,  15,   35,    15,     1;
  1,  31,  155,   155,    31,    1;
  1,  63,  651,  1395,   651,   63,   1;
  1, 127, 2667, 11811, 11811, 2667, 127, 1;

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.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 698.
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

T. D. Noe, Rows n=0..50 of triangle, flattened
Octavio A. Agustín-Aquino, Archimedes' quadrature of the parabola and minimal covers, arXiv:1602.05279 [math.CO], 2016.
J. A. de Azcarraga and J. A. Macfarlane, Group Theoretical Foundations of Fractional Supersymmetry arXiv:hep-th/9506177, 1995.
Geoffrey Critzer, Combinatorics of Vector Spaces over Finite Fields, Master's thesis, Emporia State University, 2018.
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.
R. Mestrovic, Lucas' theorem: its generalizations, extensions and applications (1878--2014), arXiv:1409.3820 [math.NT], 2014.
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)
Eric W. Weisstein, q-Binomial Coefficient.
Wikipedia, q-binomial
Index entries for sequences related to binary linear codes
Index entries for sequences related to Gaussian binomial coefficients

Cf. A006516, A218449, A135950 (matrix inverse), A000225 (k=1), A006095 (k=2), A006096 (k=3), A139382.
Cf. this sequence (q=2), A022167 (q=3), A022168 (q=4), A022169 (q=5), A022170 (q=6), A022171 (q=7), A022172 (q=8), A022173 (q=9), A022174 (q=10), A022175 (q=11), A022176 (q=12), A022177 (q=13), A022178 (q=14), A022179 (q=15), A022180 (q=16), A022181 (q=17), A022182 (q=18), A022183 (q=19), A022184 (q=20), A022185 (q=21), A022186 (q=22), A022187 (q=23), A022188 (q=24).
Analogous triangles for other q: A015109 (q=-2), A015110 (q=-3), A015112 (q=-4), A015113 (q=-5), A015116 (q=-6), A015117 (q=-7), A015118 (q=-8), A015121 (q=-9), A015123 (q=-10), A015124 (q=-11), A015125 (q=-12), A015129 (q=-13), A015132 (q=-14), A015133 (q=-15).

q:=2; [[k le 0 select 1 else (&*[(1-q^(n-j))/(1-q^(j+1)): j in [0..(k-1)]]): k in [0..n]]: n in [0..20]]; // G. C. Greubel, Nov 17 2018

A005329 := proc(n)
   mul( 2^i-1,i=1..n) ;
end proc:
A022166 := proc(n,m)
   A005329(n)/A005329(n-m)/A005329(m) ;
end proc: # R. J. Mathar, Nov 14 2011

Table[QBinomial[n, k, 2], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 08 2016 *)
(* S stands for qStirling2 *) S[n_, k_, q_] /; 1 <= k <= n := S[n - 1, k - 1, q] + Sum[q^j, {j, 0, k - 1}]*S[n - 1, k, q]; S[n_, 0, ] := KroneckerDelta[n, 0]; S[0, k, ] := KroneckerDelta[0, k]; S[, , ] = 0;
T[n_, k_] /; n >= k := Sum[Binomial[n, j]*S[n - j, n - k, q]*(q - 1)^(k - j) /. q -> 2, {j, 0, k}];
Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 08 2020, after Vladimir Kruchinin *)

T(n,k)=polcoeff(x^k/prod(j=0,k,1-2^j*x+x*O(x^n)),n) \\ Paul D. Hanna, Oct 28 2006

qp = matpascal(9,2);
for(n=1,#qp,for(k=1,n,print1(qp[n,k],", "))) \\ Gerald McGarvey, Dec 05 2009

{q=2; T(n,k) = if(k==0,1, if (k==n, 1, if (k<0 || nG. C. Greubel, May 27 2018

def T(n,k): return gaussian_binomial(n,k).subs(q=2) # Ralf Stephan, Mar 02 2014

G.f.: A(x,y) = Sum_{k>=0} y^k/Product_{j=0..k} (1 - 2^j*x). - Paul D. Hanna, Oct 28 2006
For k = 1,2,3,... the expansion of exp( Sum_{n >= 1} (2^(k*n) - 1)/(2^n - 1)*x^n/n ) gives the o.g.f. for the k-th diagonal of the triangle (k = 1 corresponds to the main diagonal). - Peter Bala, Apr 07 2015
T(n,k) = T(n-1,k-1) + q^k * T(n-1,k). - Peter A. Lawrence, Jul 13 2017
T(m+n,k) = Sum_{i=0..k} q^((k-i)*(m-i)) * T(m,i) * T(n,k-i), q=2 (see the Sved link, page 337). - Werner Schulte, Apr 09 2019
T(n,k) = Sum_{j=0..k} qStirling2(n-j,n-k)*C(n,j) where qStirling2(n,k) is A139382. - Vladimir Kruchinin, Mar 04 2020

A076831 Triangle T(n,k) read by rows giving number of inequivalent binary linear [n,k] codes (n >= 0, 0 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1, 1, 6, 16, 22, 16, 6, 1, 1, 7, 23, 43, 43, 23, 7, 1, 1, 8, 32, 77, 106, 77, 32, 8, 1, 1, 9, 43, 131, 240, 240, 131, 43, 9, 1, 1, 10, 56, 213, 516, 705, 516, 213, 56, 10, 1, 1, 11, 71, 333, 1060, 1988, 1988

Offset: 0

N. J. A. Sloane, Nov 21 2002

"The familiar appearance of the first few rows [...] provides a good example of the perils of too hasty extrapolation in mathematics." - Slepian.

The difference between this triangle and the one for which it can be so easily mistaken is A250002. - Tilman Piesk, Nov 10 2014.

			     k    0   1   2   3    4    5    6    7    8   9  10  11        sum
   n
   0      1                                                           1
   1      1   1                                                       2
   2      1   2   1                                                   4
   3      1   3   3   1                                               8
   4      1   4   6   4    1                                         16
   5      1   5  10  10    5    1                                    32
   6      1   6  16  22   16    6    1                               68
   7      1   7  23  43   43   23    7    1                         148
   8      1   8  32  77  106   77   32    8    1                    342
   9      1   9  43 131  240  240  131   43    9   1                848
  10      1  10  56 213  516  705  516  213   56  10   1           2297
  11      1  11  71 333 1060 1988 1988 1060  333  71  11   1       6928

M. Wild, Enumeration of binary and ternary matroids and other applications of the Brylawski-Lucas Theorem, Preprint No. 1693, Tech. Hochschule Darmstadt, 1994

Harald Fripertinger, Isometry Classes of Codes.
Harald Fripertinger, Wnk2: Number of the isometry classes of all binary (n,k)-codes. [This is a rectangular array whose lower triangle contains T(n,k).]
H. Fripertinger and A. Kerber, Isometry classes of indecomposable linear codes. In: G. Cohen, M. Giusti, T. Mora (eds), Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 11th International Symposium, AAECC 1995, Lect. Notes Comp. Sci. 948 (1995), pp. 194-204. [Apparently, the notation for T(n,k) is W_{nk2}; see p. 197.]
Petros Hadjicostas, Generating function for column k=4.
Petros Hadjicostas, Generating function for column k=5.
Petros Hadjicostas, Generating function for column k=6.
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.
David Slepian, Some further theory of group codes, Bell System Tech. J. 39(5) (1960), 1219-1252.
David Slepian, Some further theory of group codes, Bell System Tech. J. 39(5) (1960), 1219-1252.
Marcel Wild, Consequences of the Brylawski-Lucas Theorem for binary matroids, European Journal of Combinatorics 17 (1996), 309-316.
Marcel Wild, The asymptotic number of inequivalent binary codes and nonisomorphic binary matroids, Finite Fields and their Applications 6 (2000), 192-202.
Marcel Wild, The asymptotic number of binary codes and binary matroids, SIAM J. Discrete Math. 19 (2005), 691-699. [This paper apparently corrects some errors in previous papers.]
Index entries for sequences related to binary linear codes

Cf. A006116, A022166, A076766 (row sums).
A034356 gives same table but with the k=0 column omitted.
Columns include A000012 (k=0), A000027 (k=1), A034198 (k=2), A034357 (k=3), A034358 (k=4), A034359 (k=5), A034360 (k=6), A034361 (k=7), A034362 (k=8).

# Fripertinger's method to find the g.f. of column k >= 2 (for small k):
def A076831col(k, length):
    G1 = PSL(k, GF(2))
    G2 = PSL(k-1, GF(2))
    D1 = G1.cycle_index()
    D2 = G2.cycle_index()
    f1 = sum(i[1]*prod(1/(1-x^j) for j in i[0]) for i in D1)
    f2 = sum(i[1]*prod(1/(1-x^j) for j in i[0]) for i in D2)
    f = (f1 - f2)/(1-x)
    return f.taylor(x, 0, length).list()
# For instance the Taylor expansion for column k = 4 gives
print(A076831col(4, 30)) # Petros Hadjicostas, Sep 30 2019

From Petros Hadjicostas, Sep 30 2019: (Start)
T(n,k) = Sum_{i = k..n} A034253(i,k) for 1 <= k <= n.
G.f. for column k=2: -(x^3 - x - 1)*x^2/((x^2 + x + 1)*(x + 1)*(x - 1)^4).
G.f. for column k=3: -(x^12 - 2*x^11 + x^10 - x^9 - x^6 + x^4 - x - 1)*x^3/((x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)*(x^2 + x + 1)^2*(x^2 + 1)*(x + 1)^2*(x - 1)^8).
G.f. for column k >= 4: modify the Sage program below (cf. function f). It is too complicated to write it here. (See also some of the links above.)
(End)

A018216 Maximal number of subgroups in a group with n elements.

Original entry on oeis.org

1, 2, 2, 5, 2, 6, 2, 16, 6, 8, 2, 16, 2, 10, 4, 67, 2, 28, 2, 22, 10, 14, 2, 54, 8, 16, 28, 28, 2, 28, 2, 374, 4, 20, 4, 78, 2, 22, 16, 76, 2, 36, 2, 40, 12, 26, 2, 236, 10, 64, 4, 46, 2, 212, 14, 98, 22, 32, 2, 80, 2, 34, 36, 2825, 4, 52, 2, 58, 4, 52, 2, 272

Offset: 1

Ola Veshta (olaveshta(AT)my-deja.com), May 23 2001

For n >= 2 a(n)>=2 with equality iff n is prime.

The minimal number of subgroups is A000005, the number of divisors of n, attained by the cyclic group of order n. - Charles R Greathouse IV, Dec 27 2016

			a(6) = 6 because there are two groups with 6 elements: C_6 with 4 subgroups and S_3 with 6 subgroups.

Eric M. Schmidt, Table of n, a(n) for n = 1..511

Cf. A061034.

a:=function(n)
  local gr, mx, t, g;
  mx := 0;
  gr := AllSmallGroups(n);
  for g in gr do
    t := Sum(ConjugacyClassesSubgroups(g),Size);
    mx := Maximum(mx, t);
  od;
  return mx;
end; # Charles R Greathouse IV, Dec 27 2016

a(n)=Maximum of {A061034(n), A083573(n)}. - Lekraj Beedassy, Oct 22 2004

(C_2)^m has A006116(m) subgroups, so this is a lower bound if n is a power of 2 (e.g., a(16) >= 67). - N. J. A. Sloane, Dec 01 2007

More terms from Victoria A. Sapko (vsapko(AT)canes.gsw.edu), Jun 13 2003

More terms from Eric M. Schmidt, Sep 07 2012

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

Original entry on oeis.org

1, 3, 11, 51, 307, 2451, 26387, 387987, 7866259, 221472147, 8703733139, 479243212179, 37070813107603, 4036214347068819, 619402703369958803, 134108807406166799763, 40994263184865380595091, 17700624176280878586721683, 10799420012335823235718509971

Offset: 0

Gaëtan Leurent, Apr 16 2012

q-binomial 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)

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

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.

Cf. A006116.

List([0..20],n->Sum([0..n],k->(2^n/2^k*Product([0..k-1],i->(2^n-2^i)/(2^k-2^i))))); # Muniru A Asiru, Aug 01 2018

Table[Sum[2^n/2^k * Product[(2^n-2^i)/(2^k-2^i),{i,0,k-1}],{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 *)

{a(n)=polcoeff(sum(m=0,n,x^m/prod(k=1,m+1,1-2^k*x+x*O(x^n))),n)} /* Paul D. Hanna, May 01 2012 */

def a(n): return sum([(2^n/2^k)*prod([(2^n-2^i)/(2^k-2^i) for i in [0..k-1]]) for k in [0..n]])

a(n) = Sum_{k=0..n} (2^n/2^k * Product_{i=0..k-1} (2^n - 2^i)/(2^k - 2^i)).
G.f.: Sum_{n>=0} x^n / Product_{k=1..n+1} (1-2^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 q-factorial of n. - _Geoffrey Critzer, Jul 15 2017
a(n) = (2^n - 1)*A006116(n-1) + A006116(n). - Geoffrey Critzer, Jul 15 2017

A190939 Subgroups of nimber addition interpreted as binary numbers.

Original entry on oeis.org

1, 3, 5, 9, 15, 17, 33, 51, 65, 85, 105, 129, 153, 165, 195, 255, 257, 513, 771, 1025, 1285, 1545, 2049, 2313, 2565, 3075, 3855, 4097, 4369, 4641, 5185, 6273, 8193, 8481, 8721, 9345, 10305, 12291, 13107, 15555, 16385, 16705, 17025, 17425, 18465, 20485, 21845

Offset: 0

Tilman Piesk, May 24 2011

Each subgroup {0,a,b,...} of nimber addition can be assigned an integer 1+2^a+2^b+...
These integers ordered by size give this sequence.
Without nimbers the sequence may be defined as follows:
The powerset af a set {0,...,n-1} with the symmetric difference as group operation forms the elementary abelian group (Z_2)^n.
The elements of the group can be numbered lexicographically from 0 to 2^n-1, with 0 representing the neutral element:
{}-->0 , {0}-->2^0=1 , {1}-->2^1=2 , {0,1}-->2^0+2^1=3 , ... , {0,...,n-1}-->2^n-1
So the subgroups of (Z_2)^n can be represented by subsets of {0,...,2^n-1}.
So each subgroup {0,a,b,...} of (Z_2)^n can be assigned an integer 1+2^a+2^b+...
For each (Z_2)^n there is a finite sequence of these numbers ordered by size, and it is the beginning of the finite sequence for (Z_2)^(n+1).
This leads to the infinite sequence:
* 1,     (1 until here for (Z_2)^0)
* 3,     (2 until here for (Z_2)^1)
* 5, 9, 15,     (5 until here for (Z_2)^2)
* 17, 33, 51, 65, 85, 105, 129, 153, 165, 195, 255, (16 until here for (Z_2)^3)
* 257, 513, 771, 1025, 1285, 1545, 2049, 2313, 2565, 3075, 3855, 4097, 4369, 4641, 5185, 6273, 8193, 8481, 8721, 9345, 10305, 12291, 13107, 15555, 16385, 16705, 17025, 17425, 18465, 20485, 21845, 23205, 24585, 26265, 26985, 32769, 33153, 33345, 33825, 34833, 36873, 38505, 39321, 40965, 42405, 43605, 49155, 50115, 52275, 61455, 65535,     (67 until here for (Z_2)^4)
* 65537, ...
The number of subgroups of (Z_2)^n is 1, 2, 5, 16, 67, 374, 2825, ... (A006116)
Comment from Tilman Piesk, Aug 27 2013: (Start)
Boolean functions correspond to integers, and belong to small equivalence classes (sec). So a sec can be seen as an infinite set of integers (represented in A227722 by the smallest one). Some secs contain only one odd integer. These unique odd integers, ordered by size, are shown in this sequence. (While the smallest integers from these secs are shown in A227963.)
(End)

			The 5 subgroups of the Klein four-group (Z_2)^2 and corresponding integers are:
{0      }     -->     2^0                     =   1
{0,1    }     -->     2^0 + 2^1               =   3
{0,  2  }     -->     2^0       + 2^2         =   5
{0,    3}     -->     2^0             + 2^3   =   9
{0,1,2,3}     -->     2^0 + 2^1 + 2^2 + 2^3   =  15

Tilman Piesk, Table of n, a(n) for n = 0..2824
Tilman Piesk, Graphical explanation of n, a(n), A227963(n) for n = 0..66
Tilman Piesk, 2825x64 submatrix of the corresponding binary array, corresponding Walsh spectra (human readable versions of these matrices)
Tilman Piesk, Subgroups of nimber addition (Wikiversity)

Cf. A227963 (the same small equivalence classes represented by entries of A227722)
Cf. A198260 (number of runs of ones in the binary strings)
Subsequences:
Cf. A051179 (2^2^n-1).
Cf. A083318 (2^n+1).
Cf. A001317 (rows of the Sierpinski triangle read like binary numbers).
Cf. A228540 (rows of negated binary Walsh matrices r.l.b.n.).
Cf. A122569 (negated iterations of the Thue-Morse sequence r.l.b.n.).

Offset changed to 0 by Tilman Piesk, Jan 25 2012

A289539 Number of ways to choose a subspace U of GF(2)^n and then choose a subspace of U.

Original entry on oeis.org

1, 3, 12, 66, 513, 5769, 95706, 2379348, 89759799, 5188919427, 463209471288, 64236626341974, 13903296824817117, 4713694025825766861, 2510421030027019810854, 2104931848782489253483752, 2783505220978001187684672531, 5813031971452642599096778614183

Offset: 0

Geoffrey Critzer, Jul 12 2017

nonn

A q-analog (q=2) of A000244.

Cf. A000244, A182176, A289537, A289538, A289541, A289542.

nn = 20; eq[z_] := Sum[z^n/FunctionExpand[QFactorial[n, q]], {n, 0, nn}];
Table[FunctionExpand[QFactorial[n, q]] /. q -> 2, {n, 0, nn}] CoefficientList[ Series[eq[z]^3 /. q -> 2, {z, 0, nn}], z]

a(n) = Sum_{k=0..n} A022166(n,k)*A006116(k).

a(n)/[n]_q! is the coefficient of x^n in the expansion of exp_q(x)^3 when q -> 2 and where exp_q(x) is the q-exponential function and [n]_q! is the q-factorial of n.

A015195 Sum of Gaussian binomial coefficients for q=9.

Original entry on oeis.org

1, 2, 12, 184, 9104, 1225248, 540023488, 652225844096, 2584219514040576, 28081351726592246272, 1001235747932175990213632, 97915621602690773814148184064, 31420034518763282871588038742544384, 27654326463468067495668136467306727743488

Offset: 0

N. J. A. Sloane, Olivier Gérard

nonn

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.
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

Vincenzo Librandi, Table of n, a(n) for n = 0..60
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

Cf. A006116, A006117, A006118, A006119, A006120, A006121, A006122.

Row sums of triangle A022173.

Total/@Table[QBinomial[n, m, 9], {n, 0, 20}, {m, 0, n}] (* Vincenzo Librandi, Nov 01 2012 *)
Flatten[{1,RecurrenceTable[{a[n]==2*a[n-1]+(9^(n-1)-1)*a[n-2],a[0]==1,a[1]==2},a,{n,1,15}]}] (* Vaclav Kotesovec, Aug 21 2013 *)

a(n) = 2*a(n-1)+(9^(n-1)-1)*a(n-2), (Goldman + Rota, 1969). - Vaclav Kotesovec, Aug 21 2013

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

A061034 Maximal number of subgroups in an Abelian group with n elements.

Original entry on oeis.org

1, 2, 2, 5, 2, 4, 2, 16, 6, 4, 2, 10, 2, 4, 4, 67, 2, 12, 2, 10, 4, 4, 2, 32, 8, 4, 28, 10, 2, 8, 2, 374, 4, 4, 4, 30, 2, 4, 4, 32, 2, 8, 2, 10, 12, 4, 2, 134, 10, 16, 4, 10, 2, 56, 4, 32, 4, 4, 2, 20, 2, 4, 12, 2825, 4, 8, 2, 10, 4, 8, 2, 96, 2, 4, 16, 10, 4, 8, 2, 134, 212, 4, 2

Offset: 1

Ola Veshta (olaveshta(AT)my-deja.com), May 26 2001

a(n) is multiplicative: if m and n are relatively prime then a(m*n) = a(n) * a(m). For n >= 2, a(n)>=2 with equality iff n is prime.

			a(16) = 67: C16 has 5 subgroups, C2 X C8 has 11 subgroups, (C2)^2 X C4 has 27 subgroups, (C2)^4 has 67 subgroups, (C4)^2 has 15 subgroups.

Eric M. Schmidt, Table of n, a(n) for n = 1..10000
Max Alekseyev, PARI scripts for various problems
G. A. Miller, On the Subgroups of an Abelian Group, The Annals of Mathematics, 2nd Ser., Vol. 6, No. 1. (1904), pp. 1-6. doi:10.2307/2007151 [See paragraph 4 entitled "Total number of subgroups in a group of order p^m". - M. F. Hasler, Dec 03 2007]
G. A. Miller, Determination of the number of subgroups of an abelian group, Bull. Amer. Math. Soc. 33 (1927), 192-194.

Cf. A006116, A018216, A083573.

{ A061034(n) = my(f=factorint(n)); prod(i=1,#f~, vecmax( apply( x->numsubgrp(f[i,1],x), partitions(f[i,2]) ) ) ); } \\ See Alekseyev link for numsubgrp(), Max Alekseyev, 2008

(C_2)^m has A006116(m) subgroups, so this is a lower bound if n is a power of 2 (e.g. a(16) >= 67). - N. J. A. Sloane, Dec 01 2007

More terms from Victoria A Sapko (vsapko(AT)canes.gsw.edu), Jun 13 2003

cp's OEIS Frontend

A135922 Inverse binomial transform of A006116, which is the sum of Gaussian binomial coefficients [n,k] for q=2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A227961 Triangle T(n,k) read by rows: how often does k appear among the first A006116(n) entries of A198260?

Views

Author

Keywords

Comments

Links

A022166 Triangle of Gaussian binomial coefficients (or q-binomial coefficients) [n,k] for q = 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

A076831 Triangle T(n,k) read by rows giving number of inequivalent binary linear [n,k] codes (n >= 0, 0 <= k <= n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Sage

Formula

A018216 Maximal number of subgroups in a group with n elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Mathematica

PARI

Sage

Formula

A190939 Subgroups of nimber addition interpreted as binary numbers.