cp's OEIS Frontend

A006095 Gaussian binomial coefficient [n, 2] for q = 2.

%I A006095 M4415 #157 Jul 07 2025 00:31:19
%S A006095 0,0,1,7,35,155,651,2667,10795,43435,174251,698027,2794155,11180715,
%T A006095 44731051,178940587,715795115,2863245995,11453115051,45812722347,
%U A006095 183251413675,733006703275,2932028910251,11728119835307,46912487729835
%N A006095 Gaussian binomial coefficient [n, 2] for q = 2.
%C A006095 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
%C A006095 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
%C A006095 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
%C A006095 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
%D A006095 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.
%D A006095 I. P. Goulden and D. M. Jackson, Combinatorial Enumeration. Wiley, NY, 1983, p. 99.
%D A006095 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A006095 M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.
%H A006095 T. D. Noe, <a href="/A006095/b006095.txt">Table of n, a(n) for n = 0..200</a>
%H A006095 L. Mariot and E. Formenti, <a href="http://openit.disco.unimib.it/~mariot/mf_counting_coprime_polynomials_2016.pdf">The number of coprime/non-coprime pairs of polynomials over F_2 with degree n and nonzero constant term</a>.
%H A006095 Ronald Orozco López, <a href="https://arxiv.org/abs/2408.08943">Generating Functions of Generalized Simplicial Polytopic Numbers and (s,t)-Derivatives of Partial Theta Function</a>, arXiv:2408.08943 [math.CO], 2024. See p. 11.
%H A006095 Ronald Orozco López, <a href="https://arxiv.org/abs/2501.11490">Simplicial d-Polytopic Numbers Defined on Generalized Fibonacci Polynomials</a>, arXiv:2501.11490 [math.CO], 2025. See p. 6.
%H A006095 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A006095 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A006095 A. I. Solomon, C.-L. Ho and G. H. E. Duchamp, <a href="http://arxiv.org/abs/1205.4958">Degrees of entanglement for multipartite systems</a>, arXiv preprint arXiv:1205.4958 [quant-ph], 2012. - _N. J. A. Sloane_, Oct 23 2012
%H A006095 M. Sved, <a href="/A006095/a006095.pdf">Gaussians and binomials</a>, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)
%H A006095 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (7,-14,8).
%F A006095 G.f.: x^2/((1-x)(1-2x)(1-4x)).
%F A006095 a(n) = (2^n - 1)*(2^(n-1) - 1)/3 = 4^n/6 - 2^(n-1) + 1/3.
%F A006095 Row sums of triangle A130324. - _Gary W. Adamson_, May 24 2007
%F A006095 a(n) = Stirling2(n+1,3) + Stirling2(n+1,4). - _Zerinvary Lajos_, Oct 04 2007; corrected by _R. J. Mathar_, Mar 19 2011
%F A006095 a(n) = A139250(2^(n-1) - 1), n >= 1. - _Omar E. Pol_, Mar 03 2011
%F A006095 a(n) = 4*a(n-1) + 2^(n-1) - 1, n >= 2. - _Vincenzo Librandi_, Mar 19 2011
%F A006095 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
%F A006095 a(n) = Sum_{k=0..n-2} 2^k*C(2*n-k-2, k), n >= 2. - _Johannes W. Meijer_, Aug 19 2013
%F A006095 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
%F A006095 a(n) = a(n-1) + A000217(A000225(n-1)), n > 0. - _Ivan N. Ianakiev_, Dec 11 2017
%F A006095 E.g.f.: (2*exp(x)-3*exp(2*x)+exp(4*x))/6. - _Paul Weisenhorn_, Aug 22 2021
%F A006095 From _Peter Bala_, Jul 01 2025: (Start)
%F A006095 G.f. assuming an offset of 0: exp( Sum_{n >= 1} b(3*n)/b(n)*x^n/n ) = 1 + 7*x + 35*x^2 + ..., where b(n) = A000225(n) = 2^n - 1.
%F A006095 The following are examples of telescoping series:
%F A006095 Sum_{n >= 2} 2^n/a(n) = 6, follows from 1 - (1/6)*Sum_{k = 2..n} 2^k/a(k) = 1/(2^n - 1).
%F A006095 Sum_{n >= 2} 2^n/(a(n)*a(n+2)) = 6/49, follows from 1 - (49/6)*Sum_{k = 2..n} 2^k/(a(k)*a(k+2)) = 1/A006096(n+2);
%F A006095 Sum_{n >= 2} 4^n/(a(n)*a(n+2)) = 26/49, follows from 13 - (49/2)*Sum_{k = 2..n} 4^k/(a(k)*a(k+2)) = A086224(n)/A006096(n+2);
%F A006095 Sum_{n >= 2} 8^n/(a(n)*a(n+2)) = 129/49, follows from 43 - (49/3)*Sum_{k = 2..n} 8^k/(a(k)*a(k+2)) = A171479(n+1)/A006096(n+2). (End)
%p A006095 a:= n-> add((4^(n-1-j) - 2^(n-1-j))/2, j=0..n-1):
%p A006095 seq(a(n), n=0..24); # _Zerinvary Lajos_, Jan 04 2007
%p A006095 A006095 := -z^2/(z-1)/(2*z-1)/(4*z-1); # _Simon Plouffe_ in his 1992 dissertation. [adapted to offset 0 by _Peter Luschny_, Jul 20 2021]
%p A006095 a := n -> (2^n - 2)*(2^n - 1)/6:
%p A006095 seq(a(n), n = 0..24); # _Peter Luschny_, Jul 20 2021
%t A006095 Join[{a=0,b=0},Table[c=6*b-8*a+1;a=b;b=c,{n,60}]] (* _Vladimir Joseph Stephan Orlovsky_, Feb 06 2011 *)
%t A006095 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 *)
%t A006095 (* Next, using elementary symmetric functions *)
%t A006095 f[k_] := 2^(k - 1); t[n_] := Table[f[k], {k, 1, n}]
%t A006095 a[n_] := SymmetricPolynomial[2, t[n]]
%t A006095 Table[a[n], {n, 2, 32}]    (* A203235 *)
%t A006095 Table[a[n]/2, {n, 2, 32}]  (* A006095 *)
%t A006095 (* _Clark Kimberling_, Dec 31 2011 *)
%t A006095 Table[QBinomial[n, 2, 2], {n, 0, 24}] (* _Arkadiusz Wesolowski_, Nov 12 2015 *)
%o A006095 (Sage) [gaussian_binomial(n,2,2) for n in range(0,25)] # _Zerinvary Lajos_, May 24 2009
%o A006095 (PARI) a(n) = (2^n - 1)*(2^(n-1) - 1)/3 \\ _Charles R Greathouse IV_, Jul 25 2011
%o A006095 (PARI) concat([0, 0], Vec(x^2/((1-x)*(1-2*x)*(1-4*x)) + O(x^50))) \\ _Altug Alkan_, Nov 12 2015
%Y A006095 First differences: A006516.
%Y A006095 Gaussian binomial coefficient [n, k] for q = 2: A000225 (k = 1), this sequence (k = 2), A006096 (k = 3), A006097 (k = 4), A006110 (k = 5), A022189 - A022195 (k = 6 thru 12).
%Y A006095 Cf. A000392, A002275, A002452, A003462, A003463, A003464, A016123, A016125, A016208, A016256, A023000, A023001, A075113, A130324, A203235.
%K A006095 nonn,easy,nice
%O A006095 0,4
%A A006095 _N. J. A. Sloane_