%I M4183
%S 0,1,6,28,120,496,2016,8128,32640,130816,523776,2096128,8386560,
%T 33550336,134209536,536854528,2147450880,8589869056,34359607296,
%U 137438691328,549755289600,2199022206976,8796090925056,35184367894528
%N a(n) = 2^(n1)*(2^n  1), n >= 0.
%C a(n) is also the number of different lines determined by pair of vertices in an ndimensional hypercube. The number of these lines modulo being parallel is in A003462.  Ola Veshta (olaveshta(AT)mydeja.com), Feb 15 2001
%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)mydeja.com), Jun 01 2001
%C a(n) is the number of nletter words formed using four distinct letters, one of which appears an odd number of times.  _Lekraj Beedassy_, Jul 22 2003 [See, e.g., the Balakrishnan reference, problems 2.67 and 2.68, p. 69.  _Wolfdieter Lang_, Jul 16 2017]
%C Number of 0's making up the central triangle in a Pascal's triangle mod 2 gasket.  _Lekraj Beedassy_, May 14 2004
%C mth triangular number, where m is the nth Mersenne number, i.e., a(n)=A000217(A000225(n)).  _Lekraj Beedassy_, May 25 2004
%C Number of walks of length 2n+1 between two nodes at distance 3 in the cycle graph C_8.  _Herbert Kociemba_, Jul 02 2004
%C The sequence of fractions a(n+1)/(n+1) is the 3rd binomial transform of (1, 0, 1/3, 0, 1/5, 0, 1/7, ...).  _Paul Barry_, Aug 05 2005
%C Number of monic irreducible polynomials of degree 2 in GF(2^n)[x].  _Max Alekseyev_, Jan 23 2006
%C (A007582(n))^2 + a(n)^2 = A007582(2n). E.g., A007582(3) = 36, a(3) = 28; A007582(6) = 2080. 36^2 + 28^2 = 2080.  _Gary W. Adamson_, Jun 17 2006
%C The sequence 6*a(n), n>=1, gives the number of edges of the Hanoi graph H_4^{n} with 4 pegs and n>=1 discs.  Daniele Parisse (daniele.parisse(AT)eads.com), Jul 28 2006
%C 8*a(n) is the total border length of the 4*n masks used when making an order n regular DNA chip, using the bidimensional Gray code suggested by Pevzner in the book "Computational Molecular Biology."  Bruno Petazzoni (bruno(AT)enix.org), Apr 05 2007
%C If we start with 1 in binary and at each step we prepend 1 and append 0, we construct this sequence: 1 110 11100 1111000 etc.; see A109241(n1).  _Artur Jasinski_, Nov 26 2007
%C Let P(A) be the power set of an nelement set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which x does not equal y.  _Ross La Haye_, Jan 02 2008
%C Wieder calls these "conjoint usual 2combinations." The set of "conjoint strict kcombinations" is the subset of conjoint usual kcombinations where the empty set and the set itself are excluded from possible selection. These numbers C(2^n  2,k), which for k = 2 (i.e., {x,y} of the power set of a set) give {1, 0, 1, 15, 91, 435, 1891, 7875, 32131, 129795, 521731, ...}.  _Ross La Haye_, Jan 15 2008
%C If n is a member of A000043 then a(n) is also a perfect number (A000396).  _Omar E. Pol_, Aug 30 2008
%C a(n) is also the number whose binary representation is A109241(n1), for n>0.  _Omar E. Pol_, Aug 31 2008
%C From _Daniel Forgues_, Nov 10 2009: (Start)
%C If we define a spoofperfect number as:
%C A spoofperfect number is a number that would be perfect if some (one or more) of its odd composite factors were wrongly assumed to be prime, i.e., taken as a spoof prime.
%C And if we define a "strong" spoofperfect number as:
%C A "strong" spoofperfect number is a spoofperfect number where sigma(n) does not reveal the compositeness of the odd composite factors of n which are wrongly assumed to be prime, i.e., taken as a spoof prime.
%C The odd composite factors of n which are wrongly assumed to be prime then have to be obtained additively in sigma(n) and not multiplicatively.
%C Then:
%C If 2^n1 is odd composite but taken as a spoof prime then 2^(n1)*(2^n  1) is an even spoof perfect number (and moreover "strong" spoofperfect).
%C For example:
%C a(8) = 2^(81)*(2^8  1) = 128*255 = 32640 (where 255 (with factors 3*5*17) is taken as a spoof prime);
%C sigma(a(8)) = (2^8  1)*(255 + 1) = 255*256 = 2*(128*255) = 2*32640 = 2n is spoofperfect (and also "strong" spoofperfect since 255 is obtained additively);
%C a(11) = 2^(111)*(2^11  1) = 1024*2047 = 2096128 (where 2047 (with factors 23*89) is taken as a spoof prime);
%C sigma(a(11)) = (2^11  1)*(2047 + 1) = 2047*2048 = 2*(1024*2047) = 2*2096128 = 2n is spoofperfect (and also "strong" spoofperfect since 2047 is obtained additively).
%C I did a Google search and didn't find anything about the distinction between "strong" versus "weak" spoofperfect numbers. Maybe some other terminology is used.
%C An example of an even "weak" spoofperfect number would be:
%C n = 90 = 2*5*9 (where 9 (with factors 3^2) is taken as a spoof prime);
%C sigma(n) = (1+2)*(1+5)*(1+9) = 3*(2*3)*(2*5) = 2*(2*5*(3^2)) = 2*90 = 2n is spoofperfect (but is not "strong" spoofperfect since 9 is obtained multiplicatively as 3^2 and is thus revealed composite).
%C Euler proved:
%C If 2^k  1 is a prime number, then 2^(k1)*(2^k  1) is a perfect number and every even perfect number has this form.
%C The following seems to be true (is there a proof?):
%C If 2^k  1 is an odd composite number taken as a spoof prime, then 2^(k1)*(2^k  1) is a "strong" spoofperfect number and every even "strong" spoofperfect number has this form?
%C There is only one known odd spoofperfect number (found by Rene Descartes) but it is a "weak" spoofperfect number (cf. 'Descartes numbers' and 'Unsolved problems in number theory' links below). (End)
%C a(n+1) = A173787(2*n+1,n); cf. A020522, A059153.  _Reinhard Zumkeller_, Feb 28 2010
%C Also, row sums of triangle A139251.  _Omar E. Pol_, May 25 2010
%C From _Gary W. Adamson_, Oct 26 2010: (Start)
%C Starting with "1" = (1, 1, 2, 4, 8, ...) convolved with A002450: (1, 5, 21, 85, 341, ...); and (1, 3, 7, 15, 31, ...) convolved with A002001: (1, 3, 12, 48, 192, ...).  _Gary W. Adamson_, Oct 26 2010
%C a(n) is also the number of toothpicks in the corner toothpick structure of A153006 after 2^n  1 stages.  _Omar E. Pol_, Nov 20 2010
%C The number of ndimensional odd theta functions of halfintegral characteristic. (Gunning, p.22)  _Michael Somos_, Jan 03 2014
%C a(n) = A000217((2^n)1) = 2^(2n1)  2^(n1) is the nearest triangular number below 2^(2n1); cf. A007582, A233327.  _Antti Karttunen_, Feb 26 2014
%C a(n) is the sum of all the remainders when all the odd numbers < 2^n are divided by each of the powers 2,4,8,...,2^n.  _J. M. Bergot_, May 07 2014
%C Let b(m,k) = number of ways to form a sequence of m selections, without replacement, from a circular array of m labeled cells, such that the first selection of a cell whose adjacent cells have already been selected (a "first connect") occurs on the kth selection. b(m,k) is defined for m >=3, and for 3 <= k <= m. Then b(m,k)/2m ignores rotations and reflection. Let m=n+2, then a(n) = b(m,m1))/2m. Reiterated, a(n) is the (m1)th column of the triangle b(m,k)/2m, whose initial rows are (1), (1 2), (2 6 4), (6 18 28 8), (24 72 128 120 16), (120 360 672 840 496 32), (720 2160 4128 5760 5312 2016 64); see A249796. Note also that b(m,3)/2m = n!, and b(m,m)/2m = 2^n. Proofs are easy.  _Tony Bartoletti_, Oct 30 2014
%C Beginning at a(1) = 1, this sequence is the sum of the first 2^(n1) numbers of the form 4*k + 1. For example, a(4) = 120 = 1 + 5 + 9 + 13 + 17 + 21 + 25 + 29.  _J. M. Bergot_, Dec 07 2014
%C a(n) is the number of edges in the (2^n  1)dimensional simplex.  _Dimitri Boscainos_, Oct 05 2015
%C a(n) is the number of linear elements in a complete plane graph in 2^n points.  _Dimitri Boscainos_, Oct 05 2015
%C a(n) is the number of linear elements in a complete parallelotope graph in n dimensions.  _Dimitri Boscainos_, Oct 05 2015
%C a(n) is the number of lattices L in Z^n such that the quotient group Z^n / L is C_4.  _Álvar Ibeas_, Nov 26 2015
%C a(n) gives the quadratic coefficient of the polynomial ((x + 1)^(2^n) + (x  1)^(2^n))/2, cf. A201461.  _Martin Renner_, Jan 14 2017
%C Let f(x)=x+2*sqrt(x) and g(x)=x2*sqrt(x). Then f(4^n*x)=b(n)*f(x)+a(n)*g(x) and g(4^n*x)=a(n)*f(x)+b(n)*g(x), where b is A007582.  _Luc Rousseau_, Dec 06 2018
%D V. K. Balakrishnan, Theory and problems of Combinatorics, "Schaum's Outline Series", McGrawHill, 1995, p. 69.
%D M. Gardner, Mathematical Carnival, "Pascal's Triangle", pp. 201 Alfred A. Knopf NY 1975.
%D Richard K. Guy, Unsolved problems in number theory, (p 72.) [From _Daniel Forgues_, Nov 10 2009]
%D R. Honsberger, Mathematical Gems, M.A.A., 1973, p. 113.
%D C. A. Pickover, Wonders of Numbers, Chap. 55, Oxford Univ. Press NY 2000.
%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="/A006516/b006516.txt">Table of n, a(n) for n=0..200</a>
%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="http://neilsloane.com/doc/tooth.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), 157191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n1)1) for n >= 2.]
%H William Banks, Ahmet Güloğlu, Wesley Nevans and Filip Saidak, Descartes numbers, Anatomy of integers, 167173, CRM Proc. Lecture Notes, 46, Amer. Math. Soc., Providence, RI, 2008. <a href="http://www.ams.org/mathscinet/pdf/2437973.pdf?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&r=1&review_format=html&s4=&s5=descartes%20number&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq">MathSciNet review</a> (subscription required).
%H F. Firoozbakht, M. F. Hasler, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Hasler/hasler2.html">Variations on Euclid's formula for Perfect Numbers</a>, JIS 13 (2010) #10.3.1.
%H R. C. Gunning, <a href="http://web.math.princeton.edu/~gunning/theta2/A">Riemann Surfaces and SecondOrder Theta Functions, SpringerVerlag, 1976.</a> See page 22.
%H Ross La Haye, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/LaHaye/lahaye5.html">Binary Relations on the Power Set of an nElement Set</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
%H V. Meally, <a href="/A006516/a006516.pdf">Letter to N. J. A. Sloane, May 1975</a>
%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992.
%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">1031 Generating Functions and Conjectures</a>, Université du Québec à Montréal, 1992.
%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>
%H Thomas Wieder, <a href="http://www.math.nthu.edu.tw/~amen/2008/070301.pdf">The number of certain kcombinations of an nset</a>, Applied Mathematics Electronic Notes, vol. 8 (2008).
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (6,8).
%F G.f.: x/((1  2*x)*(1  4*x)).
%F E.g.f. for a(n+1), n>=0: 2*exp(4*x)  exp(2*x).
%F a(n) = 2^(n1)*StirlingS2(n+1,2), n>=0, with StirlingS2(n,m)=A008277(n,m).
%F Second column of triangle A075497.
%F a(n) = StirlingS2(2^n,2^n1) = binomial(2^n,2).  _Ross La Haye_, Jan 12 2008
%F a(n+1) = 4*a(n) + 2^n.  _Philippe Deléham_, Feb 20 2004
%F Convolution of 4^n and 2^n.  _Ross La Haye_, Oct 29 2004
%F a(n+1) = Sum_{k=0..n} Sum_{j=0..n} 4^(nj)*binomial(j,k).  _Paul Barry_, Aug 05 2005
%F a(n+2) = 6*a(n+1)  8*a(n), a(1) = 1, a(2) = 6.  Daniele Parisse (daniele.parisse(AT)eads.com), Jul 28 2006 [Typo corrected by _Yosu Yurramendi_, Aug 06 2008]
%F Row sums of triangle A134346. Also, binomial transform of A048473: (1, 5, 17, 53, 161, ...); double bt of A151821: (1, 4, 8, 16, 32, 64, ...) and triple bt of A010684: (1, 3, 1, 3, 1, 3, ...).  _Gary W. Adamson_, Oct 21 2007
%F a(n) = 3*StirlingS2(n+1,4) + StirlingS2(n+2,3).  _Ross La Haye_, Jun 01 2008
%F a(n) = ((4^n  2^n)/2  2^(n1))/4, n>=1.  _Zerinvary Lajos_, Jun 05 2009
%F a(n) = A153006(2^n1).  _Omar E. Pol_, Nov 20 2010
%e G.f. = x + 6*x^2 + 28*x^3 + 120*x^4 + 496*x^5 + 2016*x^6 + 8128*x^7 + 32640*x^8 + ...
%p GBC := proc(n,k,q) local i; mul( (q^(ni)1)/(q^(ki)1),i=0..k1); end; # define qary Gaussian binomial coefficient [ n,k ]_q
%p [ seq(GBC(n+1,2,2)GBC(n,2,2), n=0..30) ]; # produces A006516
%p A006516:=1/(4*z1)/(2*z1); # _Simon Plouffe_ in his 1992 dissertation
%p seq(binomial(2^n, 2), n=0..19); # _Zerinvary Lajos_, Feb 22 2008
%t Table[2^(n  1)(2^n  1), {n, 0, 30}] (* or *) LinearRecurrence[{6, 8}, {0, 1}, 30] (* _Harvey P. Dale_, Jul 15 2011 *)
%o (Sage) [lucas_number1(n,6,8) for n in xrange(0, 24)] # _Zerinvary Lajos_, Apr 22 2009
%o (Sage) [(4^n  2^n)/2 for n in xrange(0,24)] # _Zerinvary Lajos_, Jun 05 2009
%o (PARI) a(n)=(1<<n1)<<(n1) \\ _Charles R Greathouse IV_, Jun 10 2011
%o (Maxima) A006516(n):=2^(n1)*(2^n  1)$ makelist(A006516(n),n,0,30); /* _Martin Ettl_, Nov 15 2012 */
%o (Haskell)
%o a006516 n = a006516_list !! n
%o a006516_list = 0 : 1 :
%o zipWith () (map (* 6) $ tail a006516_list) (map (* 8) a006516_list)
%o  _Reinhard Zumkeller_, Oct 25 2013
%o (MAGMA) [2^(n1)*(2^n  1): n in [0..30]]; // _Vincenzo Librandi_, Oct 31 2014
%o (PARI) vector(100, n, n; 2^(n1)*(2^n1)) \\ _Altug Alkan_, Oct 06 2015
%o (Python) for n in range(0, 30): print(2**(n1)*(2**n  1), end=', ') # _Stefano Spezia_, Dec 06 2018
%o (GAP) List([0..25],n>2^(n1)*(2^n1)); # _Muniru A Asiru_, Dec 06 2018
%Y Equals A006095(n+1)  A006095(n). In other words, A006095 gives the partial sums.
%Y Cf. A007582, A010036, A016290, A003462, A079598, A134346, A048473, A151821, A010684.
%Y Cf. A000043, A000396.  _Omar E. Pol_, Aug 30 2008
%Y Cf. A109241, A139251, A153006.  _Omar E. Pol_, Aug 31 2008, May 25 2010, Nov 20 2010
%Y Cf. A002450, A002001.  _Gary W. Adamson_, Oct 26 2010
%Y Cf. A049072, A000384, A201461, A005059 (binomial transform, and special 5letter words).
%K nonn,nice,easy
%O 0,3
%A _N. J. A. Sloane_
%E Corrected by _Philippe Deléham_, Sep 17 2009
