login
a(n) = 2^(n-1)*(1+2^n).
(Formerly M2849)
67

%I M2849 #143 Sep 09 2024 09:35:19

%S 1,3,10,36,136,528,2080,8256,32896,131328,524800,2098176,8390656,

%T 33558528,134225920,536887296,2147516416,8590000128,34359869440,

%U 137439215616,549756338176,2199024304128,8796095119360,35184376283136,140737496743936,562949970198528

%N a(n) = 2^(n-1)*(1+2^n).

%C Let G_n be the elementary Abelian group G_n = (C_2)^n for n >= 1: A006516 is the number of times the number -1 appears in the character table of G_n and A007582 is the number of times the number 1. Together the two sequences cover all the values in the table, i.e., A006516(n) + A007582(n) = 2^(2n). - Ahmed Fares (ahmedfares(AT)my-deja.com), Jun 01 2001

%C Number of walks of length 2n+1 between two adjacent vertices in the cycle graph C_8. Example: a(1)=3 because in the cycle ABCDEFGH we have three walks of length 3 between A and B: ABAB, ABCB and AHAB. - _Emeric Deutsch_, Apr 01 2004

%C Smallest number containing in its binary representation two equal non-overlapping subwords of length n: A097295(a(n))=n and A097295(m)<n for m<a(n). - _Reinhard Zumkeller_, Aug 04 2004

%C a(n)^2 + (A006516(n))^2 = a(2n). E.g., a(3) = 36, A006516(3) = 28, a(6) = 2080. 36^2 + 28^2 = 2080. - _Gary W. Adamson_, Jun 17 2006

%C Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either x equals y or x does not equal y. - _Ross La Haye_, Jan 02 2008

%C Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A). This is just a simpler statement of my previous comment for this sequence. - _Ross La Haye_, Jan 10 2008

%C For n>0: A000120(a(n))=2, A023414(a(n))=2*(n-1), A087117(a(n))=n-1. - _Reinhard Zumkeller_, Jun 23 2009

%C a(n+1) written in base 2: 11, 1010, 100100, 10001000, 1000010000, ..., i.e., number 1, n times 0, number 1, n times 0 (A163449(n)). - _Jaroslav Krizek_, Jul 27 2009

%C a(n) for n >= 1 is a bisection of A001445(n+1). - _Jaroslav Krizek_, Aug 14 2009

%C Related to A102573: letting T(q,r) be the coefficient of n^(r+1) in the polynomial 2^(q-n)/n times sum_{k=0..n} binomial(n,k)*k^q, then A007582(x)= sum_{k=0..x-1} T(x,k)*2^k. - _John M. Campbell_, Nov 16 2011

%C a(n) gives the number of pairs (r, s) such that 0 <= r <= s <= (2^n)-1 that satisfy AND(r, s, XOR(r, s)) = 0. - _Ramasamy Chandramouli_, Aug 30 2012

%C a(n) = A000217(2^n) = 2^(2n-1) + 2^(n-1) is the nearest triangular number above 2^(2n-1); cf. A006516, A233327. - _Antti Karttunen_, Feb 26 2014

%C Consider the quantum spin-1/2 chain with even number of sites L (physics, condensed matter theory). The spectrum of the Hamiltonian can be classified according to symmetries. If the only symmetry of the spin Hamiltonian is Parity, i.e., reflection with respect to the middle of the chain (see e.g. the transverse-field Ising model with open boundary conditions), then the dimension of the p=+1 parity sector is given by a(n) with n=L/2. - _Marin Bukov_, Mar 11 2016

%C a(n) is also the total number of words of length n, over an alphabet of four letters, of which one of them appears an even number of times. See the Lekraj Beedassy, Jul 22 2003, comment on A006516 (4-letter odd case), and the Balakrishnan reference there. For the 1- to 11-letter cases, see the crossrefs. - _Wolfdieter Lang_, Jul 17 2017

%C a(n) is the number of nonisomorphic spanning trees of the cyclic snake formed with n+1 copies of the cycle on 4 vertices. A cyclic snake is a connected graph whose block-cutpoint is a path and all its n blocks are isomorphic to the cycle C_m. - _Christian Barrientos_, Sep 05 2024

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A007582/b007582.txt">Table of n, a(n) for n=0..200</a>

%H M. Archibald, A. Blecher, A. Knopfmacher, M. E. Mays, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Archibald/arch3.html">Inversions and Parity in Compositions of Integers</a>, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.

%H S. Hong and J. H. Kwak, <a href="http://dx.doi.org/10.1002/jgt.3190170509">Regular fourfold coverings with respect to the identity automorphism</a>, J. Graph Theory, 17 (1993), 621-627.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=168">Encyclopedia of Combinatorial Structures 168</a>

%H Ross La Haye, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/LaHaye/lahaye5.html">Binary Relations on the Power Set of an n-Element Set</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.

%H Mircea Merca, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL15/Merca1/merca6.html">A Note on Cosine Power Sums</a>, J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (6,-8)

%F G.f.: (1-3*x)/((1-2*x)*(1-4*x)). C(1+2^n, 2) where C(n, 2) is n-th triangular number A000217.

%F Binomial transform of A007051. Inverse binomial transform of A081186. - _Paul Barry_, Apr 07 2003

%F E.g.f.: exp(3*x)*cosh(x). - _Paul Barry_, Apr 07 2003

%F a(n) = Sum_{k=0..floor(n/2)} C(n, 2*k)*3^(n-2*k). - _Paul Barry_, May 08 2003

%F a(n+1) = 4*a(n) - 2^n; see also A049775. a(n) = 2^(n-1)*A000051(n). - _Philippe Deléham_, Feb 20 2004

%F a(n) = 6*a(n-1) - 8*a(n-2). - _Emeric Deutsch_, Apr 01 2004

%F Row sums of triangle A134308. - _Gary W. Adamson_, Oct 19 2007

%F a(n) = StirlingS2(2^n + 1,2^n) = 1 + 2*StirlingS2(n+1,2) + 3*StirlingS2(n+1,3) + 3*StirlingS2(n+1,4) = StirlingS2(n+2,2) + 3(StirlingS2(n+1,3) + StirlingS2(n+1,4)). - _Ross La Haye_, Mar 01 2008

%F a(n) = StirlingS2(2^n + 1,2^n) = 1 + 2*StirlingS2(n+1,2) + 3*StirlingS2(n+1,3) + 3*StirlingS2(n+1,4) = StirlingS2(n+2,2) + 3(StirlingS2(n+1,3) + StirlingS2(n+1,4)). - _Ross La Haye_, Apr 02 2008

%F a(n) = A000079(n) + A006516(n). - _Yosu Yurramendi_, Aug 06 2008

%F a(n) = A028403(n+1) / 4. - _Jaroslav Krizek_, Jul 27 2009

%F a(n) = Sum_{k=-floor(n/4)..floor(n/4)} binomial(2*n,n+4*k)/2. - _Mircea Merca_, Jan 28 2012

%F G.f.: Q(0)/2 where Q(k) = 1 + 2^k/(1 - 2*x/(2*x + 2^k/Q(k+1) )); (continued fraction ). - _Sergei N. Gladkovskii_, Apr 10 2013

%F a(n) = Sum_{k=1..2^n} k. - _Joerg Arndt_, Sep 01 2013

%F a(n) = (1/3) * Sum_{k=2^n..2^(n+1)} k. - _J. M. Bergot_, Jan 26 2015

%F a(n+1) = 2*a(n) + 4^n. - _Yuchun Ji_, Mar 10 2017

%p seq(binomial(-2^n, 2), n=0..23); # _Zerinvary Lajos_, Feb 22 2008

%t Table[ Binomial[2^n + 1, 2], {n, 0, 23}] (* _Robert G. Wilson v_, Jul 30 2004 *)

%t LinearRecurrence[{6,-8},{1,3},30] (* _Harvey P. Dale_, Apr 08 2013 *)

%o (PARI) a(n)=if(n<0,0,2^(n-1)*(1+2^n))

%o (PARI) a(n)=sum(k=-n\4,n\4,binomial(2*n+1,n+1+4*k))

%o (Maxima) A007582(n):=2^(n-1)*(1+2^n)$ makelist(A007582(n),n,0,30); /* _Martin Ettl_, Nov 15 2012 */

%o (Magma) [Binomial(2^n + 1, 2) : n in [0..30]]; // _Wesley Ivan Hurt_, Jul 03 2020

%Y Cf. A000217, A049773, A049775.

%Y Cf. A006516.

%Y Cf. A134308.

%Y Cf. A000225, A000392, A032263, A028243, A000079.

%Y Cf. A102573.

%Y The number of words of length n with m letters, one of them appearing an even number of times is for m = 1..11: A000035, A011782, A007051, A007582, A081186, A081187, A081188, A081189, A081190, A060531, A081192. - _Wolfdieter Lang_, Jul 17 2017

%K nonn,easy,nice

%O 0,2

%A _Simon Plouffe_