|
| |
|
|
A006116
|
|
Sum of Gaussian binomial coefficients [n,k] for q=2 and k=0..n.
(Formerly M1501)
|
|
7
| |
|
|
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; 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). [From Jonathan Vos Post, Mar 11 2010]
|
|
|
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.
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.
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
| S. Hitzemann, W. Hochstattler, On the combinatorics of Galois numbers, Discr. Math. 310 (2010) 3551-3557, Galois Numbers G_{n}^(2).
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
Contribution 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)
|
|
|
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,..]);
[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.
|
|
|
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] (* From Jean-François Alcover, Jul 21 2011 *)
|
|
|
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))) [From Paul D. Hanna, Nov 29 2008]
|
|
|
CROSSREFS
| Cf. A006516. Row sums of A022166.
Cf. A005329, A083906. [From Paul D. Hanna, Nov 29 2008]
Sequence in context: A019503 A019504 A005163 * A122082 A002631 A107948
Adjacent sequences: A006113 A006114 A006115 * A006117 A006118 A006119
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
