CINXE.COM

A000078 - OEIS

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> <html> <head> <link rel="stylesheet" href="/styles.css"> <meta name="format-detection" content="telephone=no"> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta name=viewport content="width=device-width, initial-scale=1"> <meta name="keywords" content="OEIS,integer sequences,Sloane" /> <title>A000078 - OEIS</title> <link rel="search" type="application/opensearchdescription+xml" title="OEIS" href="/oeis.xml"> <script> var myURL = "\/A000078" function redir() { var host = document.location.hostname; if(host != "oeis.org" && host != "127.0.0.1" && !/^([0-9.]+)$/.test(host) && host != "localhost" && host != "localhost.localdomain") { document.location = "https"+":"+"//"+"oeis"+".org/" + myURL; } } function sf() { if(document.location.pathname == "/" && document.f) document.f.q.focus(); } </script> </head> <body bgcolor=#ffffff onload="redir();sf()"> <div class=loginbar> <div class=login> <a href="/login?redirect=%2fA000078">login</a> </div> </div> <div class=center><div class=top> <center> <div class=donors> The OEIS is supported by <a href="http://oeisf.org/#DONATE">the many generous donors to the OEIS Foundation</a>. </div> <div class=banner> <a href="/"><img class=banner border="0" width="600" src="/banner2021.jpg" alt="A000078 - OEIS"></a> </div> </center> </div></div> <div class=center><div class=pagebody> <div class=searchbarcenter> <form name=f action="/search" method="GET"> <div class=searchbargreet> <div class=searchbar> <div class=searchq> <input class=searchbox maxLength=1024 name=q value="" title="Search Query"> </div> <div class=searchsubmit> <input type=submit value="Search" name=go> </div> <div class=hints> <span class=hints><a href="/hints.html">Hints</a></span> </div> </div> <div class=searchgreet> (Greetings from <a href="/welcome">The On-Line Encyclopedia of Integer Sequences</a>!) </div> </div> </form> </div> <div class=sequence> <div class=space1></div> <div class=line></div> <div class=seqhead> <div class=seqnumname> <div class=seqnum> A000078 </div> <div class=seqname> Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) for n &gt;= 4 with a(0) = a(1) = a(2) = 0 and a(3) = 1. <br><font size=-1>(Formerly M1108 N0423)</font> </div> </div> <div class=scorerefs> 101 </div> </div> <div> <div class=seqdatabox> <div class=seqdata>0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, 1055026, 2033628, 3919944, 7555935, 14564533, 28074040, 54114452, 104308960, 201061985, 387559437, 747044834, 1439975216, 2775641472</div> <div class=seqdatalinks> (<a href="/A000078/list">list</a>; <a href="/A000078/graph">graph</a>; <a href="/search?q=A000078+-id:A000078">refs</a>; <a href="/A000078/listen">listen</a>; <a href="/history?seq=A000078">history</a>; <a href="/search?q=id:A000078&fmt=text">text</a>; <a href="/A000078/internal">internal format</a>) </div> </div> </div> <div class=entry> <div class=section> <div class=sectname>OFFSET</div> <div class=sectbody> <div class=sectline>0,6</div> </div> </div> <div class=section> <div class=sectname>COMMENTS</div> <div class=sectbody> <div class=sectline>a(n) is the number of compositions of n-3 with no part greater than 4. Example: a(7) = 8 because we have 1+1+1+1 = 2+1+1 = 1+2+1 = 3+1 = 1+1+2 = 2+2 = 1+3 = 4. - <a href="/wiki/User:Emeric_Deutsch">Emeric Deutsch</a>, Mar 10 2004</div> <div class=sectline>In other words, a(n) is the number of ways of putting stamps in one row on an envelope using stamps of denominations 1, 2, 3 and 4 cents so as to total n-3 cents [P贸lya-Szeg艖]. - <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Jul 28 2012</div> <div class=sectline>a(n+4) is the number of 0-1 sequences of length n that avoid 1111. - <a href="/wiki/User:David_Callan">David Callan</a>, Jul 19 2004</div> <div class=sectline>a(n) is the number of matchings in the graph obtained by a zig-zag triangulation of a convex (n-3)-gon. Example: a(8) = 15 because in the triangulation of the convex pentagon ABCDEA with diagonals AD and AC we have 15 matchings: the empty set, seven singletons and {AB,CD}, {AB,DE}, {BC,AD}, {BC,DE}, {BC,EA}, {CD,EA} and {DE,AC}. - <a href="/wiki/User:Emeric_Deutsch">Emeric Deutsch</a>, Dec 25 2004</div> <div class=sectline>Number of permutations satisfying -k &lt;= p(i)-i &lt;= r, i=1..n-3, with k = 1, r = 3. - <a href="/wiki/User:Vladimir_Baltic">Vladimir Baltic</a>, Jan 17 2005</div> <div class=sectline>For n &gt;= 0, a(n+4) is the number of palindromic compositions of 2*n+1 into an odd number of parts that are not multiples of 4. In addition, a(n+4) is also the number of Sommerville symmetric cyclic compositions (= bilaterally symmetric cyclic compositions) of 2*n+1 into an odd number of parts that are not multiples of 4. - <a href="/wiki/User:Petros_Hadjicostas">Petros Hadjicostas</a>, Mar 10 2018</div> <div class=sectline>a(n) is the number of ways to tile a hexagonal double-strip (two rows of adjacent hexagons) containing (n-4) cells with hexagons and double-hexagons (two adjacent hexagons). - <a href="/wiki/User:Ziqian_Jin">Ziqian Jin</a>, Jul 28 2019</div> <div class=sectline>The term &quot;tetranacci number&quot; was coined by Mark Feinberg (1963; see <a href="/A000073" title="Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) for n &gt;= 3 with a(0) = a(1) = 0 and a(2) = 1.">A000073</a>). - <a href="/wiki/User:Amiram_Eldar">Amiram Eldar</a>, Apr 16 2021</div> <div class=sectline>a(n) is the number of ways to tile a skew double-strip of n-3 cells using squares and all possible &quot;dominos&quot;, as seen in Ziqian Jin's article, below. Here is the skew double-strip corresponding to n=15, with 12 cells:</div> <div class=sectline> ___ ___ ___ ___ ___ ___</div> <div class=sectline> | | | | | | |</div> <div class=sectline> _|___|___|___|___|_ _|___|</div> <div class=sectline>| | | | | | |</div> <div class=sectline>|___|___|___|___|___|___|,</div> <div class=sectline>and here are the three possible &quot;domino&quot; tiles:</div> <div class=sectline> ___ ___</div> <div class=sectline> | | | |</div> <div class=sectline> _| _| |_ |_ _______</div> <div class=sectline>| | | | | |</div> <div class=sectline>|___|, |___|, |_______|.</div> <div class=sectline>As an example, here is one of the a(15) = 1490 ways to tile the skew double-strip of 12 cells:</div> <div class=sectline> ___ ___ _______ _______</div> <div class=sectline> | | | | | | |</div> <div class=sectline> _|___|_ |___|_ _|_ _| _|</div> <div class=sectline>| | | | | |</div> <div class=sectline>|_______|___|___|___|___|. - <a href="/wiki/User:Greg_Dresden">Greg Dresden</a>, Jun 05 2024</div> </div> </div> <div class=section> <div class=sectname>REFERENCES</div> <div class=sectbody> <div class=sectline>Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.</div> <div class=sectline>G. P贸lya and G. Szeg艖, Problems and Theorems in Analysis, Springer-Verlag, NY, 2 vols., 1972, Vol. 1, p. 1, Problems 3 and 4.</div> <div class=sectline>J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, Princeton, NJ, 1978.</div> <div class=sectline>N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).</div> <div class=sectline>N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).</div> </div> </div> <div class=section> <div class=sectname>LINKS</div> <div class=sectbody> <div class=sectline>Indranil Ghosh, <a href="/A000078/b000078.txt">Table of n, a(n) for n = 0..3505</a> (terms 0..200 from T. D. Noe)</div> <div class=sectline>Abdullah A莽ikel, Amrouche Said, Hacene Belbachir, and Nurettin Irmak, <a href="https://doi.org/10.55730/1300-0098.3416">On k-generalized Lucas sequence with its triangle</a>, Turkish J. Math. (2023) Vol. 47, No. 4, Art. 6, 1129-1143. See p. 1130.</div> <div class=sectline>Isha Agarwal, Matvey Borodin, Aidan Duncan, Kaylee Ji, Tanya Khovanova, Shane Lee, Boyan Litchev, Anshul Rastogi, Garima Rastogi, and Andrew Zhao, <a href="https://arxiv.org/abs/2006.13002">From Unequal Chance to a Coin Game Dance: Variants of Penney's Game</a>, arXiv:2006.13002 [math.HO], 2020.</div> <div class=sectline>Tom谩s Aguilar-Fraga, Jennifer Elder, Rebecca E. Garcia, Kimberly P. Hadaway, Pamela E. Harris, Kimberly J. Harry, Imhotep B. Hogan, Jakeyl Johnson, Jan Kretschmann, Kobe Lawson-Chavanu, J. Carlos Mart铆nez Mori, Casandra D. Monroe, Daniel Qui帽onez, Dirk Tolson III, and Dwight Anderson Williams II, <a href="https://arxiv.org/abs/2311.14055">Interval and L-interval Rational Parking Functions</a>, arXiv:2311.14055 [math.CO], 2023.</div> <div class=sectline>Kassie Archer and Aaron Geary, <a href="https://arxiv.org/abs/2312.14351">Powers of permutations that avoid chains of patterns</a>, arXiv:2312.14351 [math.CO], 2023. See p. 15.</div> <div class=sectline>Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 307-309.</div> <div class=sectline>Vladimir Baltic, <a href="http://pefmath.etf.rs/vol4num1/AADM-Vol4-No1-119-135.pdf">On the number of certain types of strongly restricted permutations</a>, Applicable Analysis and Discrete Mathematics 4(1) (2010), 119-135.</div> <div class=sectline>Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo Pinzani, <a href="http://arxiv.org/abs/1601.07723">Non-overlapping matrices</a>, arXiv:1601.07723 [cs.DM], 2016.</div> <div class=sectline>Martin Burtscher, Igor Szczyrba, and Rafa艂 Szczyrba, <a href="http://www.emis.de/journals/JIS/VOL18/Szczyrba/sz3.html">Analytic Representations of the n-anacci Constants and Generalizations Thereof</a>, J. Integer Seq. 18 (2015), Article 15.4.5.</div> <div class=sectline>P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integer Seq. 3 (2000), Article 00.1.5.</div> <div class=sectline>S. A. Corey and Otto Dunkel, <a href="http://www.jstor.org/stable/2299550">Problem 2803</a>, Amer. Math. Monthly 33 (1926), 229-232.</div> <div class=sectline>F. Michel Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Dekking/dekk4.html">Morphisms, Symbolic Sequences, and Their Standard Forms</a>, J. Integer Seq. 19 (2016), Article 16.1.1.</div> <div class=sectline>Emeric Deutsch, <a href="http://www.jstor.org/stable/3219192">Problem 1613: A recursion in four parts</a>, Math. Mag. 75(1) (2002), 64-65.</div> <div class=sectline>脰m眉r Deveci, Zafer Ad谋g眉zel and Taha Do臒an, <a href="https://doi.org/10.7546/nntdm.2020.26.1.179-190">On the Generalized Fibonacci-circulant-Hurwitz numbers</a>, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 1, 179-190.</div> <div class=sectline>G. P. B. Dresden and Z. Du, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Dresden/dresden6.html">A Simplified Binet Formula for k-Generalized Fibonacci Numbers</a>, J. Integer Seq. 17 (2014), Article 14.4.7.</div> <div class=sectline>M. Feinberg, <a href="http://www.fq.math.ca/Scanned/1-3/feinberg.pdf">Fibonacci-Tribonacci</a>, Fib. Quart. 1(3) (1963), 71-74.</div> <div class=sectline>Taras Goy and Mark Shattuck, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Shattuck/shattuck20.html">Some Toeplitz-Hessenberg determinant identities for the tetranacci numbers</a>, J. Integer Seq. 23 (2020), Article 20.6.8.</div> <div class=sectline>Petros Hadjicostas, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Hadjicostas/hadji2.html">Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence</a>, J. Integer Seq. 19 (2016), Article 16.8.2.</div> <div class=sectline>Petros Hadjicostas, <a href="https://doi.org/10.2140/moscow.2020.9.173">Generalized colored circular palindromic compositions</a>, Moscow Journal of Combinatorics and Number Theory, 9(2) (2020), 173-186.</div> <div class=sectline>P. Hadjicostas and L. Zhang, <a href="https://www.fq.math.ca/Papers1/55-1/HadjicostasZhang10252016.pdf">Sommerville's symmetrical cyclic compositions of a positive integer with parts avoiding multiples of an integer</a>, Fibonacci Quarterly 55 (2017), 54-73.</div> <div class=sectline>Russell Jay Hendel, <a href="https://arxiv.org/abs/2107.03549">A Method for Uniformly Proving a Family of Identities</a>, arXiv:2107.03549 [math.CO], 2021.</div> <div class=sectline>F. T. Howard and Curtis Cooper, <a href="https://www.fq.math.ca/Papers1/49-3/HowardCooper.pdf">Some identities for r-Fibonacci numbers</a>, Fibonacci Quarterly 49 (2011), 231-242.</div> <div class=sectline>INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=11">Encyclopedia of Combinatorial Structures 11</a></div> <div class=sectline>Ziqian Jin, <a href="https://arxiv.org/abs/1907.09935">Tetrancci Identities With Squares, Dominoes, And Hexagonal Double Strips</a>, arXiv:1907.09935 [math.GM], 2019.</div> <div class=sectline>Omar Khadir, L谩szl贸 N茅meth, and L谩szl贸 Szalay, <a href="https://doi.org/10.1007/s00025-024-02284-3">Tiling of dominoes with ranked colors</a>, Results in Math. (2024) Vol. 79, Art. No. 253. See p. 2.</div> <div class=sectline>Sergey Kirgizov, <a href="https://arxiv.org/abs/2201.00782">Q-bonacci words and numbers</a>, arXiv:2201.00782 [math.CO], 2022.</div> <div class=sectline>W. C. Lynch, <a href="http://www.fq.math.ca/Scanned/8-1/lynch.pdf">The t-Fibonacci numbers and polyphase sorting</a>, Fib. Quart., 8 (1970), 6-22.</div> <div class=sectline>T. Mansour and M. Shattuck, <a href="http://arxiv.org/abs/1410.6943">A monotonicity property for generalized Fibonacci sequences</a>, arXiv:1410.6943 [math.CO], 2014.</div> <div class=sectline>Tony D. Noe and Jonathan Vos Post, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Noe/noe5.html">Primes in Fibonacci n-step and Lucas n-step Sequences,</a> J. Integer Seq. 8 (2005), Article 05.4.4.</div> <div class=sectline>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.</div> <div class=sectline>Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992</div> <div class=sectline>H. Prodinger, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Prodinger2/prod31.html">Counting Palindromes According to r-Runs of Ones Using Generating Functions</a>, J. Integer Seq. 17 (2014), Article 14.6.2; odd length middle 0, r=3.</div> <div class=sectline>Helmut Prodinger and Sarah J. Selkirk, <a href="https://arxiv.org/abs/1906.08336">Sums of squares of Tetranacci numbers: A generating function approach</a>, arXiv:1906.08336 [math.NT], 2019.</div> <div class=sectline>Lan Qi and Zhuoyu Chen, <a href="https://doi.org/10.3390/sym11121476">Identities Involving the Fourth-Order Linear Recurrence Sequence</a>, Symmetry 11(12) (2019), 1476, 8pp.</div> <div class=sectline>J. L. Ram铆rez and V. F. Sirvent, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p38">A Generalization of the k-Bonacci Sequence from Riordan Arrays</a>, Electron. J. Combin. 22(1) (2015), #P1.38.</div> <div class=sectline>O. Turek, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Turek/turek3.html">Abelian Complexity Function of the Tribonacci Word</a>, J. Integer Seq. 18 (2015), Article 15.3.4.</div> <div class=sectline>Kai Wang, <a href="https://www.researchgate.net/publication/344295426_IDENTITIES_FOR_GENERALIZED_ENNEANACCI_NUMBERS">Identities for generalized enneanacci numbers</a>, Generalized Fibonacci Sequences (2020).</div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>.</div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TetranacciNumber.html">Tetranacci Number</a>.</div> <div class=sectline>L. Zhang and P. Hadjicostas, <a href="http://www.appliedprobability.org/data/files/TMS%20articles/40_2_3.pdf">On sequences of independent Bernoulli trials avoiding the pattern '11..1'</a>, Math. Scientist, 40 (2015), 89-96.</div> <div class=sectline><a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,1).</div> </div> </div> <div class=section> <div class=sectname>FORMULA</div> <div class=sectbody> <div class=sectline>a(n) = <a href="/A001630" title="Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4), with a(0)=a(1)=0, a(2)=1, a(3)=2.">A001630</a>(n) - a(n-1). - <a href="/wiki/User:Henry_Bottomley">Henry Bottomley</a></div> <div class=sectline>G.f.: x^3/(1 - x - x^2 - x^3 - x^4). - <a href="/wiki/User:Simon_Plouffe">Simon Plouffe</a> in his 1992 dissertation</div> <div class=sectline>G.f.: x^3 / (1 - x / (1 - x / (1 + x^3 / (1 + x / (1 - x / (1 + x)))))). - <a href="/wiki/User:Michael_Somos">Michael Somos</a>, May 12 2012</div> <div class=sectline>G.f.: Sum_{n &gt;= 0} x^(n+3) * (Product_{k = 1..n} (k + k*x + k*x^2 + x^3)/(1 + k*x + k*x^2 + k*x^3)). - <a href="/wiki/User:Peter_Bala">Peter Bala</a>, Jan 04 2015</div> <div class=sectline>a(n) = term (1,4) in the 4 X 4 matrix [1,1,0,0; 1,0,1,0; 1,0,0,1; 1,0,0,0]^n. - <a href="/wiki/User:Alois_P._Heinz">Alois P. Heinz</a>, Jun 12 2008</div> <div class=sectline>Another form of the g.f.: f(z) = (z^3 - z^4)/(1 - 2*z + z^5), then a(n) = Sum_{i=0..floor((n-3)/5)} (-1)^i*binomial(n-3-4*i, i)*2^(n - 3 - 5*i) - Sum_{i=0..floor((n-4)/5)} (-1)^i*binomial(n-4-4*i, i)*2^(n - 4 - 5*i) with natural convention Sum_{i=m..n} alpha(i) = 0 for m &gt; n. - <a href="/wiki/User:Richard_Choulet">Richard Choulet</a>, Feb 22 2010</div> <div class=sectline>a(n+3) = Sum_{k=1..n} Sum_{i=k..n} [(5*k-i mod 4) = 0] * binomial(k, (5*k-i)/4) *(-1)^((i-k)/4) * binomial(n-i+k-1,k-1), n &gt; 0. - <a href="/wiki/User:Vladimir_Kruchinin">Vladimir Kruchinin</a>, Aug 18 2010 [Edited by <a href="/wiki/User:Petros_Hadjicostas">Petros Hadjicostas</a>, Jul 26 2020, so that the formula agrees with the offset of the sequence]</div> <div class=sectline>Sum_{k=0..3*n} a(k+b) * <a href="/A008287" title="Triangle of quadrinomial coefficients, row n is the sequence of coefficients of (1 + x + x^2 + x^3)^n.">A008287</a>(n,k) = a(4*n+b), b &gt;= 0 (&quot;quadrinomial transform&quot;). - <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Nov 10 2010</div> <div class=sectline>G.f.: x^3*(1 + x*(G(0)-1)/(x+1)) where G(k) = 1 + (1+x+x^2+x^3)/(1-x/(x+1/G(k+1) )); (recursively defined continued fraction). - <a href="/wiki/User:Sergei_N._Gladkovskii">Sergei N. Gladkovskii</a>, Jan 26 2013</div> <div class=sectline>Starting (1, 2, 4, 8, ...) = the INVERT transform of (1, 1, 1, 1, 0, 0, 0, ...). - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, May 13 2013</div> <div class=sectline>a(n) ~ c*r^n, where c = 0.079077767399388561146007... and r = 1.92756197548292530426195... = <a href="/A086088" title="Decimal expansion of the limit of the ratio of consecutive terms in the tetranacci sequence A000078.">A086088</a> (One of the roots of the g.f. denominator polynomial is 1/r.). - <a href="/wiki/User:Fung_Lam">Fung Lam</a>, Apr 29 2014</div> <div class=sectline>a(n) = 2*a(n-1) - a(n-5), n &gt;= 5. - <a href="/wiki/User:Bob_Selcoe">Bob Selcoe</a>, Jul 06 2014</div> <div class=sectline>From <a href="/wiki/User:Ziqian_Jin">Ziqian Jin</a>, Jul 28 2019: (Start)</div> <div class=sectline>a(2*n+5) = a(n+4)^2 + a(n+3)^2 + a(n+2)^2 + 2*a(n+3)*(a(n+2) + a(n+1)).</div> <div class=sectline>a(n) - 1 = a(n-2) + 2*a(n-3) + 3*(a(n-4) + a(n-5) + ... + a(2) + a(1)), n &gt;= 4. (End)</div> <div class=sectline>a(n) = (Sum_{i=0..n-1} a(i)*<a href="/A073817" title="Tetranacci numbers with different initial conditions: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) starting with a(0)=4, a(1)=1,...">A073817</a>(n-i))/(n-3) for n &gt; 3. - <a href="/wiki/User:Greg_Dresden">Greg Dresden</a> and <a href="/wiki/User:Advika_Srivastava">Advika Srivastava</a>, Sep 28 2019</div> </div> </div> <div class=section> <div class=sectname>EXAMPLE</div> <div class=sectbody> <div class=sectline>From <a href="/wiki/User:Petros_Hadjicostas">Petros Hadjicostas</a>, Mar 10 2018: (Start)</div> <div class=sectline>For n = 3, we get a(3+4) = a(7) = 8 palindromic compositions of 2*n+1 = 7 into an odd number of parts that are not a multiple of 4. They are the following: 7 = 1+5+1 = 3+1+3 = 2+3+2 = 1+2+1+2+1 = 2+1+1+1+2 = 1+1+3+1+1 = 1+1+1+1+1+1+1. If we put these compositions on a circle, they become bilaterally symmetric cyclic compositions of 2*n+1 = 7.</div> <div class=sectline>For n = 4, we get a(4+4) = a(8) = 15 palindromic compositions of 2*n + 1 = 9 into an odd number of parts that are not a multiple of 4. They are the following: 9 = 3+3+3 = 2+5+2 = 1+7+1 = 1+1+5+1+1 = 2+1+3+1+2 = 1+2+3+2+1 = 1+3+1+3+1 = 3+1+1+1+3 = 2+2+1+2+2 = 2+1+1+1+1+1+2 = 1+2+1+1+1+2+1 = 1+1+2+1+2+1+1 = 1+1+1+3+1+1+1 = 1+1+1+1+1+1+1+1+1.</div> <div class=sectline>As <a href="/wiki/User:David_Callan">David Callan</a> points out in the comments above, for n &gt;= 1, a(n+4) is also the number of 0-1 sequences of length n that avoid 1111. For example, for n = 5, a(5+4) = a(9) = 29 is the number of binary strings of length n that avoid 1111. Out of the 2^5 = 32 binary strings of length n = 5, the following do not avoid 1111: 11111, 01111, and 11110. (End)</div> </div> </div> <div class=section> <div class=sectname>MAPLE</div> <div class=sectbody> <div class=sectline>a:= n-&gt; (&lt;&lt;1|1|0|0&gt;, &lt;1|0|1|0&gt;, &lt;1|0|0|1&gt;, &lt;1|0|0|0&gt;&gt;^n)[1, 4]: seq(a(n), n=0..50); # <a href="/wiki/User:Alois_P._Heinz">Alois P. Heinz</a>, Jun 12 2008</div> </div> </div> <div class=section> <div class=sectname>MATHEMATICA</div> <div class=sectbody> <div class=sectline>CoefficientList[Series[x^3/(1-x-x^2-x^3-x^4), {x, 0, 50}], x]</div> <div class=sectline>LinearRecurrence[{1, 1, 1, 1}, {0, 0, 0, 1}, 50] (* <a href="/wiki/User:Vladimir_Joseph_Stephan_Orlovsky">Vladimir Joseph Stephan Orlovsky</a>, May 25 2011 *)</div> <div class=sectline>(* From <a href="/wiki/User:Eric_W._Weisstein">Eric W. Weisstein</a>, Nov 09 2017 *)</div> <div class=sectline>Table[RootSum[-1 -# -#^2 -#^3 +#^4 &amp;, 10#^n +157#^(n+1) -103 #^(n+2) +16#^(n+3) &amp;]/563, {n, 0, 40}]</div> <div class=sectline>Table[RootSum[#^4 -#^3 -#^2 -# -1 &amp;, #^(n-2)/(-#^3 +6# -1) &amp;], {n, 0, 40}] (* End *)</div> </div> </div> <div class=section> <div class=sectname>PROG</div> <div class=sectbody> <div class=sectline>(PARI) {a(n) = if( n&lt;0, 0, polcoeff( x^3 / (1 - x - x^2 - x^3 - x^4) + x * O(x^n), n))}</div> <div class=sectline>(Maxima) a(n):=sum(sum(if mod(5*k-i, 4)&gt;0 then 0 else binomial(k, (5*k-i)/4)*(-1)^((i-k)/4)*binomial(n-i+k-1, k-1), i, k, n), k, 1, n); \\ <a href="/wiki/User:Vladimir_Kruchinin">Vladimir Kruchinin</a>, Aug 18 2010</div> <div class=sectline>(Haskell)</div> <div class=sectline>import Data.List (tails, transpose)</div> <div class=sectline>a000078 n = a000078_list !! n</div> <div class=sectline>a000078_list = 0 : 0 : 0 : f [0, 0, 0, 1] where</div> <div class=sectline> f xs = y : f (y:xs) where</div> <div class=sectline> y = sum $ head $ transpose $ take 4 $ tails xs</div> <div class=sectline>-- <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Jul 06 2014, Apr 28 2011</div> <div class=sectline>(Python)</div> <div class=sectline><a href="/A000078" title="Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) for n &gt;= 4 with a(0) = a(1) = a(2) = 0 and a(3) = 1.">A000078</a> = [0, 0, 0, 1]</div> <div class=sectline>for n in range(4, 100):</div> <div class=sectline> <a href="/A000078" title="Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) for n &gt;= 4 with a(0) = a(1) = a(2) = 0 and a(3) = 1.">A000078</a>.append(<a href="/A000078" title="Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) for n &gt;= 4 with a(0) = a(1) = a(2) = 0 and a(3) = 1.">A000078</a>[n-1]+<a href="/A000078" title="Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) for n &gt;= 4 with a(0) = a(1) = a(2) = 0 and a(3) = 1.">A000078</a>[n-2]+<a href="/A000078" title="Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) for n &gt;= 4 with a(0) = a(1) = a(2) = 0 and a(3) = 1.">A000078</a>[n-3]+<a href="/A000078" title="Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) for n &gt;= 4 with a(0) = a(1) = a(2) = 0 and a(3) = 1.">A000078</a>[n-4])</div> <div class=sectline># <a href="/wiki/User:Chai_Wah_Wu">Chai Wah Wu</a>, Aug 20 2014</div> <div class=sectline>(Magma) [n le 4 select Floor(n/4) else Self(n-1)+Self(n-2)+Self(n-3)+Self(n-4): n in [1..50]]; // <a href="/wiki/User:Vincenzo_Librandi">Vincenzo Librandi</a>, Jan 29 2016</div> <div class=sectline>(GAP) a:=[0, 0, 0, 1];; for n in [5..40] do a[n]:=a[n-1]+a[n-2]+a[n-3]+a[n-4]; od; a; # <a href="/wiki/User:Muniru_A_Asiru">Muniru A Asiru</a>, Mar 11 2018</div> </div> </div> <div class=section> <div class=sectname>CROSSREFS</div> <div class=sectbody> <div class=sectline>Row 4 of arrays <a href="/A048887" title="Array T read by antidiagonals, where T(m,n) = number of compositions of n into parts &lt;= m.">A048887</a> and <a href="/A092921" title="Array F(k, n) read by descending antidiagonals: k-generalized Fibonacci numbers in row k &gt;= 1, starting (0, 1, 1, ...), for ...">A092921</a> (k-generalized Fibonacci numbers).</div> <div class=sectline>First differences are in <a href="/A001631" title="Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4), with initial conditions a(0..3) = (0, 0, 1, 0).">A001631</a>.</div> <div class=sectline>Cf. <a href="/A008287" title="Triangle of quadrinomial coefficients, row n is the sequence of coefficients of (1 + x + x^2 + x^3)^n.">A008287</a> (quadrinomial coefficients) and <a href="/A073817" title="Tetranacci numbers with different initial conditions: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) starting with a(0)=4, a(1)=1,...">A073817</a> (tetranacci with different initial conditions).</div> <div class=sectline>Sequence in context: <a href="/A066369" title="Number of subsets of {1, ..., n} with no four terms in arithmetic progression.">A066369</a> <a href="/A239555" title="Number of compositions of n such that the first part is 1 and the second differences of the parts are in {-5,...,5}.">A239555</a> <a href="/A275544" title="Number of distinct terms at a given iteration of the Collatz (or 3x+1) map starting with 0.">A275544</a> * <a href="/A176503" title="Leading column of triangle in A176463.">A176503</a> <a href="/A262333" title="Number of (n+3) X (1+3) 0..1 arrays with each row and column divisible by 9, read as a binary number with top and left being...">A262333</a> <a href="/A293335" title="Least integer k such that k/2^n &gt; sqrt(1/5).">A293335</a></div> <div class=sectline>Adjacent sequences: <a href="/A000075" title="Number of positive integers &lt;= 2^n of form 2 x^2 + 3 y^2.">A000075</a> <a href="/A000076" title="Number of integers &lt;= 2^n of form 4 x^2 + 4 x y + 5 y^2.">A000076</a> <a href="/A000077" title="Number of positive integers &lt;= 2^n of form x^2 + 6 y^2.">A000077</a> * <a href="/A000079" title="Powers of 2: a(n) = 2^n.">A000079</a> <a href="/A000080" title="Number of nonisomorphic minimal triangle graphs.">A000080</a> <a href="/A000081" title="Number of unlabeled rooted trees with n nodes (or connected functions with a fixed point).">A000081</a></div> </div> </div> <div class=section> <div class=sectname>KEYWORD</div> <div class=sectbody> <div class=sectline><span title="a sequence of nonnegative numbers">nonn</span>,<span title="it is very easy to produce terms of sequence">easy</span>,<span title="an exceptionally nice sequence">nice</span></div> </div> </div> <div class=section> <div class=sectname>AUTHOR</div> <div class=sectbody> <div class=sectline><a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a></div> </div> </div> <div class=section> <div class=sectname>EXTENSIONS</div> <div class=sectbody> <div class=sectline>Definition augmented (with 4 initial terms) by <a href="/wiki/User:Daniel_Forgues">Daniel Forgues</a>, Dec 02 2009</div> <div class=sectline>Deleted certain dangerous or potentially dangerous links. - <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Jan 30 2021</div> </div> </div> <div class=section> <div class=sectname>STATUS</div> <div class=sectbody> <div class=sectline>approved</div> </div> </div> </div> <div class=space10></div> </div> </div></div> <p> <div class=footerpad></div> <div class=footer> <center> <div class=bottom> <div class=linksbar> <a href="/">Lookup</a> <a href="/wiki/Welcome"><font color="red">Welcome</font></a> <a href="/wiki/Main_Page"><font color="red">Wiki</font></a> <a href="/wiki/Special:RequestAccount">Register</a> <a href="/play.html">Music</a> <a href="/plot2.html">Plot 2</a> <a href="/demo1.html">Demos</a> <a href="/wiki/Index_to_OEIS">Index</a> <a href="/webcam">WebCam</a> <a href="/Submit.html">Contribute</a> <a href="/eishelp2.html">Format</a> <a href="/wiki/Style_Sheet">Style Sheet</a> <a href="/transforms.html">Transforms</a> <a href="/ol.html">Superseeker</a> <a href="/recent">Recents</a> </div> <div class=linksbar> <a href="/community.html">The OEIS Community</a> </div> <div class=linksbar> Maintained by <a href="http://oeisf.org">The OEIS Foundation Inc.</a> </div> <div class=dbinfo>Last modified November 24 09:28 EST 2024. Contains 378056 sequences.</div> <div class=legal> <a href="/wiki/Legal_Documents">License Agreements, Terms of Use, Privacy Policy</a> </div> </div> </center> </div> </body> </html>

Pages： 1 2 3 4 5 6 7 8 9 10