|
%I M3518 N1428 #379 Mar 22 2024 08:28:59
%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). Essentially same as Pisot sequences E(4, 16), L(4, 16), P(4, 16), T(4, 16). 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 Hankel transform of A076035. - _Philippe Deléham_, Feb 28 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 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 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 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 H. W. Gould, Combinatorial Identities, 1972, eq. (1.93), p. 12.
%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 G. Dresden and Y. Li, <a href="https://arxiv.org/abs/2210.04322">Periodic Weighted Sums of Binomial Coefficients</a>, arXiv:2210.04322 [math.NT], 2022.
%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 Roudy El Haddad, <a href="https://arxiv.org/abs/2101.09089">Recurrent Sums and Partition Identities</a>, arXiv:2101.09089 [math.NT], 2021.
%H Roudy El Haddad, <a href="https://doi.org/10.7546/nntdm.2022.28.2.167-199">A generalization of multiple zeta value. Part 1: Recurrent sums</a>. Notes on Number Theory and Discrete Mathematics, 28(2), 2022, 167-199, DOI: 10.7546/nntdm.2022.28.2.167-199.
%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; arXiv:0911.4975 [math.NT], 2009.
%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 Robert Schneider, <a href="https://doi.org/10.1007/s40993-016-0039-5">Partition zeta functions</a>, Research in Number Theory, 2(1):9., 2016.
%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 A000005(a(n)) = A005408(n+1). - _Reinhard Zumkeller_, Mar 04 2007
%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*Stirling2(n+1, 4) + 6*Stirling2(n+1, 3) + 3*Stirling2(n+1, 2) + 1 = 2*Stirling2(2^n, 2^n - 1) + Stirling2(n+1, 2) + 1. - _Ross La Haye_, Jun 26 2008
%F a(n) = A159991(n)/A001024(n) = A047653(n) + A181765(n). A160700(a(n)) = A010685(n). - _Reinhard Zumkeller_, May 02 2009
%F a(n) = A188915(A006127(n)). - _Reinhard Zumkeller_, Apr 14 2011
%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) = Sum_{k = 0..n} binomial(2*k + x, k)*binomial(2*(n - k) - x, n - k) for every real number x. - _Rui Duarte_ and António Guedes de Oliveira, Feb 16 2013
%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
%F a(n) = denominator(zeta_star({2}_(n + 1))/zeta(2*n + 2)) where zeta_star is the multiple zeta star values and ({2}_n) represents (2, ..., 2) where the multiplicity of 2 is n. - _Roudy El Haddad_, Feb 22 2022
%F a(n) = 1 + 3*Sum_{k=0..n} binomial(2*n, n+k)*(k|9), where (k|9) is the Jacobi symbol. - _Greg Dresden_, Oct 11 2022
%F a(n) = Sum_{k = 0..n} binomial(2*n+1, 2*k) = Sum_{k = 0..n} binomial(2*n+1, 2*k+1). - _Sela Fried_, Mar 23 2023
%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.
%Y Cf. A083420.
%K easy,nonn,nice,core
%O 0,2
%A _N. J. A. Sloane_
%E Partially edited by _Joerg Arndt_, Mar 11 2010
| 