|
|
A006095
|
|
Gaussian binomial coefficient [n,2] for q=2.
(Formerly M4415)
|
|
68
|
|
|
0, 0, 1, 7, 35, 155, 651, 2667, 10795, 43435, 174251, 698027, 2794155, 11180715, 44731051, 178940587, 715795115, 2863245995, 11453115051, 45812722347, 183251413675, 733006703275, 2932028910251, 11728119835307, 46912487729835
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Number of 4-block coverings of an n-set where every element of the set is covered by exactly 3 blocks (if offset is 3), so a(n) = (1/4!)*(4^n-6*2^n+8). - Vladeta Jovovic, Feb 20 2001
Number of non-coprime pairs of polynomials (f,g) with binary coefficients where both f and g have degree n+1 and nonzero constant term. - Luca Mariot and Enrico Formenti, Sep 26 2016
Number of triplets found from the integers 1 to 2^n-1 by converting to binary and performing an XOR operation on the corresponding bits of each pair. Defining addition in this carryless way (0+0=1+1=0, 0+1=1+0=1), each triplet (A,B,C) has the property A+B=C, A+C=B and B+C=A. For example, n=3 gives the 7 triplets (1,2,3), (1,4,5), (1,6,7), (2,4,6), (2,5,7), (3,4,7) and (3,5,6). Each integer appears in the set of triplets 2^(n-1)-1 times, for example 3 for n=3. - Ian Duff, Oct 05 2019
Number of 2-dimensional vector subspaces of (Z_2)^n, so also number of Klein subgroups of the group (C_2)^n. - Robert FERREOL, Jul 28 2021
|
|
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.
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
|
|
|
FORMULA
|
G.f.: x^2/((1-x)(1-2x)(1-4x)).
a(n) = (2^n - 1)*(2^(n-1) - 1)/3 = 4^n/6 - 2^(n-1) + 1/3.
a(0) = 0, a(1) = 0, a(2) = 1, a(n) = 7*a(n-1) - 14*a(n-2) + 8*a(n-3). - Harvey P. Dale, Jul 22 2011
a(n) = Sum_{i=0..n-2, j=i..n-2} 2^{i+j} = 2^0 * (2^0 + 2^1 + ... + 2^(n-2)) + 2^1 * (2^1 + 2^2 + ... + 2^(n-2)) + ... + 2^(n-2) * 2^(n-2), n>1. - J. M. Bergot, May 08 2017
|
|
MAPLE
|
a:= n-> add((4^(n-1-j) - 2^(n-1-j))/2, j=0..n-1):
a := n -> (2^n - 2)*(2^n - 1)/6:
|
|
MATHEMATICA
|
CoefficientList[Series[x^2/((1-x)(1-2x)(1-4x)), {x, 0, 30}], x] (* or *) LinearRecurrence[{7, -14, 8}, {0, 0, 1}, 30] (* Harvey P. Dale, Jul 22 2011 *)
(* Next, using elementary symmetric functions *)
f[k_] := 2^(k - 1); t[n_] := Table[f[k], {k, 1, n}]
a[n_] := SymmetricPolynomial[2, t[n]]
Table[a[n], {n, 2, 32}] (* A203235 *)
Table[a[n]/2, {n, 2, 32}] (* A006095 *)
|
|
PROG
|
(Sage) [gaussian_binomial(n, 2, 2) for n in range(0, 25)] # Zerinvary Lajos, May 24 2009]
(PARI) concat([0, 0], Vec(x^2/((1-x)*(1-2*x)*(1-4*x)) + O(x^50))) \\ Altug Alkan, Nov 12 2015
|
|
CROSSREFS
|
Cf. A000225, A000392, A002275, A002452, A003462, A003463, A003464, A016123, A016125, A016208, A016256, A023000, A023001, A075113, A130324, A203235.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|