|
| |
|
|
A022166
|
|
Triangle of Gaussian binomial coefficients (or q-binomial coefficients) [n,k] for q = 2.
|
|
80
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
Also number of distinct binary linear [n,k] codes.
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
|
|
|
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.
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
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(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
|
|
|
EXAMPLE
|
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;
|
|
|
MAPLE
|
mul( 2^i-1, i=1..n) ;
end proc:
|
|
|
MATHEMATICA
|
(* 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}];
|
|
|
PROG
|
(PARI) 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
(PARI) qp = matpascal(9, 2);
for(n=1, #qp, for(k=1, n, print1(qp[n, k], ", "))) \\ Gerald McGarvey, Dec 05 2009
(PARI) {q=2; T(n, k) = if(k==0, 1, if (k==n, 1, if (k<0 || n<k, 0, T(n-1, k-1) + q^k*T(n-1, k))))};
for(n=0, 10, for(k=0, n, print1(T(n, k), ", "))) \\ G. C. Greubel, May 27 2018
(Sage) def T(n, k): return gaussian_binomial(n, k).subs(q=2) # Ralf Stephan, Mar 02 2014
(Magma) 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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
