The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000302 Powers of 4: a(n) = 4^n. (Formerly M3518 N1428) 420

%I M3518 N1428

%S 1,4,16,64,256,1024,4096,16384,65536,262144,1048576,4194304,16777216,

%T 67108864,268435456,1073741824,4294967296,17179869184,68719476736,

%U 274877906944,1099511627776,4398046511104,17592186044416,70368744177664,281474976710656

%N Powers of 4: a(n) = 4^n.

%C Same as Pisot sequences E(1, 4), L(1, 4), P(1, 4), T(1, 4). See A008776 for definitions of Pisot sequences.

%C The convolution square root of this sequence is A000984, the central binomial coefficients: C(2n,n). - _T. D. Noe_, Jun 11 2002

%C With P(n) being the number of integer partitions of n, p(i) as the number of parts of the i-th partition of n, d(i) as the number of different parts of the i-th partition of n, m(i, j) the multiplicity of the j-th part of the i-th partition of n, one has a(n) = Sum_{i = 1..P(n)} p(i)!/(Product_{j = 1..d(i)} m(i, j)!) * 2^(n-1). - _Thomas Wieder_, May 18 2005

%C Sums of rows of the triangle in A122366. - _Reinhard Zumkeller_, Aug 30 2006

%C A000005(a(n)) = A005408(n+1). - _Reinhard Zumkeller_, Mar 04 2007

%C Hankel transform of A076035. - _Philippe Deléham_, Feb 28 2009

%C a(n) = A159991(n)/A001024(n) = A047653(n) + A181765(n). A160700(a(n)) = A010685(n). - _Reinhard Zumkeller_, May 02 2009

%C Equals the Catalan sequence: (1, 1, 2, 5, 14, ...), convolved with A032443: (1, 3, 11, 42, ...). - _Gary W. Adamson_, May 15 2009

%C a(n) = A188915(A006127(n)). - _Reinhard Zumkeller_, Apr 14 2011

%C Sum of coefficients of expansion of (1 + x + x^2 + x^3)^n.

%C a(n) is number of compositions of natural numbers into n parts less than 4. For example, a(2) = 16 since there are 16 compositions of natural numbers into 2 parts less than 4.

%C The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 1, a(n) equals the number of 4-colored compositions of n such that no adjacent parts have the same color. - _Milan Janjic_, Nov 17 2011

%C Squares in A002984. - _Reinhard Zumkeller_, Dec 28 2011

%C a(n) is the minimum number whose arithmetic derivative is n times the number itself: 1' = 0 = 0 * 1; 4' = 4 = 1 * 4; 16' = 32 = 2 * 16; 64' = 192 = 3 * 64, etc. - _Paolo P. Lava_, Feb 21 2012

%C Row sums of Pascal's triangle using the rule that going left increases the value by a factor of k = 3. For example, the first three rows are {1}, {3, 1}, and {9, 6, 1}. Using this rule gives row sums as (k+1)^n. - _Jon Perry_, Oct 11 2012

%C Sum_{k = 0..n} binomial(2*k + l, k)*binomial(2*(n - k) - l, n - k) for every real number l. - _Rui Duarte_ and António Guedes de Oliveira, Feb 16 2013

%C First differences of A002450. - _Omar E. Pol_, Feb 20 2013

%C Sum of all peak heights in Dyck paths of semilength n+1. - _David Scambler_, Apr 22 2013

%C Powers of 4 exceed powers of 2 by A020522 which is the m-th oblong number A002378(m), m being the n-th Mersenne number A000225(n); hence, we may write, a(n) = A000079(n) + A002378(A000225(n)). - _Lekraj Beedassy_, Jan 17 2014

%C a(n) is equal to 1 plus the sum for 0 < k < 2^n of the numerators and denominators of the reduced fractions k/2^n. - _J. M. Bergot_, Jul 13 2015

%C Binomial transform of A000244. - _Tony Foster III_, Oct 01 2016

%C From _Ilya Gutkovskiy_, Oct 01 2016: (Start)

%C Number of nodes at level n regular 4-ary tree.

%C Partial sums of A002001. (End)

%C Satisfies Benford's law [Berger-Hill, 2011]. - _N. J. A. Sloane_, Feb 08 2017

%C Also the number of connected dominating sets in the (n+1)-barbell graph. - _Eric W. Weisstein_, Jun 29 2017

%C Side length of the cells at level n in a pyramid scheme where a square grid is decomposed into overlapping 2 X 2 blocks (cf. Kropatsch, 1985). - _Felix Fröhlich_, Jul 04 2019

%C a(n-1) is the number of 3-compositions of n; see Hopkins & Ouvry reference. - _Brian Hopkins_, Aug 15 2020

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994, eq. (5.39), p. 187.

%D D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.

%H T. D. Noe, <a href="/A000302/b000302.txt">Table of n, a(n) for n = 0..100</a>

%H Arno Berger and Theodore P. Hill, <a href="https://works.bepress.com/tphill/74/">Benford's law strikes back: no simple explanation in sight for mathematical gem</a>, The Mathematical Intelligencer 33.1 (2011): 85-91.

%H Isabel Cação, Helmuth R. Malonek, Maria Irene Falcão, and Graça Tomaz, <a href="https://www.emis.de/journals/JIS/VOL21/Falcao/falcao2.html">Combinatorial Identities Associated with a Multidimensional Polynomial Sequence</a>, J. Int. Seq., Vol. 21 (2018), Article 18.7.4.

%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H R. Duarte and A. G. de Oliveira, <a href="http://arxiv.org/abs/1302.2100">Short note on the convolution of binomial coefficients</a>, arXiv preprint arXiv:1302.2100 [math.CO], 2013 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Duarte/duarte3.html">J. Int. Seq. 16 (2013) #13.7.6</a>.

%H R. K. Guy, <a href="/A000346/a000346.pdf">Letter to N. J. A. Sloane</a>

%H Brian Hopkins and Stéphane Ouvry, <a href="https://arxiv.org/abs/2008.04937">Combinatorics of Multicompositions</a>, arXiv:2008.04937 [math.CO], 2020.

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

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

%H Milan Janjić, <a href="https://www.emis.de/journals/JIS/VOL21/Janjic2/janjic103.html">Pascal Matrices and Restricted Words</a>, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.

%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>

%H Craig Knecht, <a href="/A000302/a000302_1.png">Number of tilings for a 6 sphinx tile repetitive unit.</a>

%H Walter G. Kropatsch, <a href="https://doi.org/10.1016/0167-8655(85)90062-5">A pyramid that grows by powers of 2</a>, Pattern Recognition Letters, Vol. 3, No. 5 (1985), 315-322 [Subscription required].

%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 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.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H Robert Price, <a href="/A000302/a000302.txt">Comments on A000302 concerning Elementary Cellular Automata</a>, Feb 26 2016.

%H Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

%H Paul K. Stockmeyer, <a href="http://arxiv.org/abs/1504.04404">The Pascal Rhombus and the Stealth Configuration</a>, arXiv preprint arXiv:1504.04404 [math.CO], 2015.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BarbellGraph.html">Barbell Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CantorDust.html">Cantor Dust</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConnectedDominatingSet.html">Connected Dominating Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ElementaryCellularAutomaton.html">Elementary Cellular Automaton</a>

%H S. Wolfram, <a href="http://wolframscience.com/">A New Kind of Science</a>

%H <a href="https://oeis.org/wiki/Index_to_Elementary_Cellular_Automata">Index to Elementary Cellular Automata</a>

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

%H <a href="/index/Rec#order_01">Index entries for linear recurrences with constant coefficients</a>, signature (4).

%H <a href="/index/Be#Benford">Index entries for sequences related to Benford's law</a>

%F a(n) = 4^n.

%F a(0) = 1; a(n) = 4*a(n-1).

%F G.f.: 1/(1-4*x).

%F E.g.f.: exp(4*x).

%F a(n) = Sum_{k = 0..n} binomial(2k, k) * binomial(2(n - k), n - k). - _Benoit Cloitre_, Jan 26 2003 [See Graham et al., eq. (5.39), p. 187. -_Wolfdieter Lang_, Aug 16 2019]

%F 1 = Sum_{n >= 1} 3/a(n) = 3/4 + 3/16 + 3/64 + 3/256 + 3/1024, ...; with partial sums: 3/4, 15/16, 63/64, 255/256, 1023/1024, ... - _Gary W. Adamson_, Jun 16 2003

%F a(n) = A001045(2*n) + A001045(2*n+1). - _Paul Barry_, Apr 27 2004

%F a(n) = Sum_{j = 0..n} 2^(n - j)*binomial(n + j, j). - Peter C. Heinig (algorithms(AT)gmx.de), Apr 06 2007

%F Hankel transform of A115967. - _Philippe Deléham_, Jun 22 2007

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

%F ((2+sqrt(4))^n - (2-sqrt(4))^n)/4. Offset 1. a(3) = 16. - Al Hakanson (hawkuu(AT)gmail.com), Dec 31 2008

%F a(n) = Sum_{k = 0..n} binomial(2*n+1, k). - _Mircea Merca_, Jun 25 2011

%F Sum_{n >= 1} mobius(n)/a(n) = 0.1710822479183... - _R. J. Mathar_, Aug 12 2012

%F a(n) = 5*a(n - 1) - 4*a(n - 2). - _Jean-Bernard François_, Sep 12 2013

%F a(n) = (2*n+1) * binomial(2*n,n) * Sum_{j=0..n} (-1)^j/(2*j+1)*binomial(n,j). - _Vaclav Kotesovec_, Sep 15 2013

%F a(n) = A000217(2^n - 1) + A000217(2^n). - _J. M. Bergot_, Dec 28 2014

%F a(n) = (2^n)^2 = A000079(n)^2. - _Doug Bell_, Jun 23 2015

%F a(n) = A002063(n)/3 - A004171(n). - _Zhandos Mambetaliyev_, Nov 19 2016

%F a(n) = (1/2) * Product_{k = 0..n} (1 + (2*n + 1)/(2*k + 1)). - _Peter Bala_, Mar 06 2018

%F a(n) = A001045(n+1)*A001045(n+2) + A001045(n)^2. - _Ezhilarasu Velayutham_, Aug 30 2019

%p A000302 := n->4^n;

%p for n from 0 to 10 do sum(2^(n-j)*binomial(n+j,j),j=0..n); od; # Peter C. Heinig (algorithms(AT)gmx.de), Apr 06 2007

%p A000302:=-1/(-1+4*z); # _Simon Plouffe_ in his 1992 dissertation.

%t Table[4^n, {n, 0, 30}] (* _Stefan Steinerberger_, Apr 01 2006 *)

%t CoefficientList[Series[1/(1 - 4 x), {x, 0, 50}], x] (* _Vincenzo Librandi_, May 29 2014 *)

%t NestList[4 # &, 1, 30] (* _Harvey P. Dale_, Mar 26 2015 *)

%t 4^Range[0, 30] (* _Eric W. Weisstein_, Jun 29 2017 *)

%t LinearRecurrence[{4}, {1}, 31] (* _Robert A. Russell_, Nov 08 2018 *)

%o (PARI) A000302(n)=4^n \\ _Michael B. Porter_, Nov 06 2009

%o (Haskell)

%o a000302 = (4 ^)

%o a000302_list = iterate (* 4) 1 -- _Reinhard Zumkeller_, Apr 04 2012

%o (Maxima) A000302(n):=4^n\$ makelist(A000302(n),n,0,30); /* _Martin Ettl_, Oct 24 2012 */

%o (Scala) (List.fill(20)(4: BigInt)).scanLeft(1: BigInt)(_ * _) // _Alonso del Arte_, Jun 22 2019

%o (Python) print([4**n for n in range(25)]) # _Michael S. Branicky_, Jan 04 2021

%Y Cf. A024036, A052539, A032443, A000351 (Binomial transform).

%Y Cf. A249307.

%K easy,nonn,nice,core

%O 0,2

%A _N. J. A. Sloane_

%E Partially edited by _Joerg Arndt_, Mar 11 2010

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 22 22:19 EDT 2021. Contains 343197 sequences. (Running on oeis4.)