login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006116 Sum of Gaussian binomial coefficients [n,k] for q=2 and k=0..n.
(Formerly M1501)
22
1, 2, 5, 16, 67, 374, 2825, 29212, 417199, 8283458, 229755605, 8933488744, 488176700923, 37558989808526, 4073773336877345, 623476476706836148, 134732283882873635911, 41128995468748254231002, 17741753171749626840952685, 10817161765507572862559462656 (list; graph; refs; listen; history; text; internal format)
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.

The subsequence of primes in this sum of Gaussian binomial coefficients begins: 2, 5, 67, no more through a(19). [Jonathan Vos Post, Mar 11 2010]

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

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

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

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

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: A239911 A275518 A005163 * A122082 A002631 A107948

Adjacent sequences:  A006113 A006114 A006115 * A006117 A006118 A006119

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 18 05:08 EST 2017. Contains 294853 sequences.