|
%I M1108 N0423 #375 Mar 11 2024 05:19:46
%S 0,0,0,1,1,2,4,8,15,29,56,108,208,401,773,1490,2872,5536,10671,20569,
%T 39648,76424,147312,283953,547337,1055026,2033628,3919944,7555935,
%U 14564533,28074040,54114452,104308960,201061985,387559437,747044834,1439975216,2775641472
%N Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) for n >= 4 with a(0) = a(1) = a(2) = 0 and a(3) = 1.
%C 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. - _Emeric Deutsch_, Mar 10 2004
%C 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ő]. - _N. J. A. Sloane_, Jul 28 2012
%C a(n+4) is the number of 0-1 sequences of length n that avoid 1111. - _David Callan_, Jul 19 2004
%C 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}. - _Emeric Deutsch_, Dec 25 2004
%C Number of permutations satisfying -k <= p(i)-i <= r, i=1..n-3, with k = 1, r = 3. - _Vladimir Baltic_, Jan 17 2005
%C For n >= 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. - _Petros Hadjicostas_, Mar 10 2018
%C 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). - _Ziqian Jin_, Jul 28 2019
%C The term "tetranacci number" was coined by Mark Feinberg (1963; see A000073). - _Amiram Eldar_, Apr 16 2021
%D Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
%D 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.
%D J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, Princeton, NJ, 1978.
%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).
%H Indranil Ghosh, <a href="/A000078/b000078.txt">Table of n, a(n) for n = 0..3505</a> (terms 0..200 from T. D. Noe)
%H 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.
%H 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.
%H 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.
%H 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.
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 307-309.
%H 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.
%H 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.
%H 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.
%H 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.
%H S. A. Corey and Otto Dunkel, <a href="http://www.jstor.org/stable/2299550">Problem 2803</a>, Amer. Math. Monthly 33 (1926), 229-232.
%H 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.
%H 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.
%H Ö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.
%H 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.
%H M. Feinberg, <a href="http://www.fq.math.ca/Scanned/1-3/feinberg.pdf">Fibonacci-Tribonacci</a>, Fib. Quart. 1(3) (1963), 71-74.
%H 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.
%H 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.
%H 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.
%H 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.
%H 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.
%H 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.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=11">Encyclopedia of Combinatorial Structures 11</a>
%H 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.
%H Sergey Kirgizov, <a href="https://arxiv.org/abs/2201.00782">Q-bonacci words and numbers</a>, arXiv:2201.00782 [math.CO], 2022.
%H 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.
%H 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.
%H 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.
%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 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.
%H 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.
%H 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.
%H 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.
%H 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.
%H 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).
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TetranacciNumber.html">Tetranacci Number</a>.
%H 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.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,1).
%F a(n) = A001630(n) - a(n-1). - _Henry Bottomley_
%F G.f.: x^3/(1 - x - x^2 - x^3 - x^4). - _Simon Plouffe_ in his 1992 dissertation
%F G.f.: x^3 / (1 - x / (1 - x / (1 + x^3 / (1 + x / (1 - x / (1 + x)))))). - _Michael Somos_, May 12 2012
%F G.f.: Sum_{n >= 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)). - _Peter Bala_, Jan 04 2015
%F 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. - _Alois P. Heinz_, Jun 12 2008
%F 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 > n. - _Richard Choulet_, Feb 22 2010
%F 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 > 0. - _Vladimir Kruchinin_, Aug 18 2010 [Edited by _Petros Hadjicostas_, Jul 26 2020, so that the formula agrees with the offset of the sequence]
%F Sum_{k=0..3*n} a(k+b) * A008287(n,k) = a(4*n+b), b >= 0 ("quadrinomial transform"). - _N. J. A. Sloane_, Nov 10 2010
%F 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). - _Sergei N. Gladkovskii_, Jan 26 2013
%F Starting (1, 2, 4, 8, ...) = the INVERT transform of (1, 1, 1, 1, 0, 0, 0, ...). - _Gary W. Adamson_, May 13 2013
%F a(n) ~ c*r^n, where c = 0.079077767399388561146007... and r = 1.92756197548292530426195... = A086088 (One of the roots of the g.f. denominator polynomial is 1/r.). - _Fung Lam_, Apr 29 2014
%F a(n) = 2*a(n-1) - a(n-5), n >= 5. - _Bob Selcoe_, Jul 06 2014
%F From _Ziqian Jin_, Jul 28 2019: (Start)
%F 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)).
%F a(n) - 1 = a(n-2) + 2*a(n-3) + 3*(a(n-4) + a(n-5) + ... + a(2) + a(1)), n >= 4. (End)
%F a(n) = (Sum_{i=0..n-1} a(i)*A073817(n-i))/(n-3) for n > 3. - _Greg Dresden_ and _Advika Srivastava_, Sep 28 2019
%e From _Petros Hadjicostas_, Mar 10 2018: (Start)
%e 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.
%e 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.
%e As _David Callan_ points out in the comments above, for n >= 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)
%p a:= n-> (<<1|1|0|0>, <1|0|1|0>, <1|0|0|1>, <1|0|0|0>>^n)[1, 4]: seq(a(n), n=0..50); # _Alois P. Heinz_, Jun 12 2008
%t CoefficientList[Series[x^3/(1-x-x^2-x^3-x^4), {x, 0, 50}], x]
%t LinearRecurrence[{1,1,1,1}, {0,0,0,1}, 50] (* _Vladimir Joseph Stephan Orlovsky_, May 25 2011 *)
%t (* From _Eric W. Weisstein_, Nov 09 2017 *)
%t Table[RootSum[-1 -# -#^2 -#^3 +#^4 &, 10#^n +157#^(n+1) -103 #^(n+2) +16#^(n+3) &]/563, {n, 0, 40}]
%t Table[RootSum[#^4 -#^3 -#^2 -# -1 &, #^(n-2)/(-#^3 +6# -1) &], {n, 0, 40}] (* End *)
%o (PARI) {a(n) = if( n<0, 0, polcoeff( x^3 / (1 - x - x^2 - x^3 - x^4) + x * O(x^n), n))}
%o (Maxima) a(n):=sum(sum(if mod(5*k-i,4)>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); \\ _Vladimir Kruchinin_, Aug 18 2010
%o (Haskell)
%o import Data.List (tails, transpose)
%o a000078 n = a000078_list !! n
%o a000078_list = 0 : 0 : 0 : f [0,0,0,1] where
%o f xs = y : f (y:xs) where
%o y = sum $ head $ transpose $ take 4 $ tails xs
%o -- _Reinhard Zumkeller_, Jul 06 2014, Apr 28 2011
%o (Python)
%o A000078 = [0,0,0,1]
%o for n in range(4, 100):
%o A000078.append(A000078[n-1]+A000078[n-2]+A000078[n-3]+A000078[n-4])
%o # _Chai Wah Wu_, Aug 20 2014
%o (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]]; // _Vincenzo Librandi_, Jan 29 2016
%o (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; # _Muniru A Asiru_, Mar 11 2018
%Y Row 4 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).
%Y First differences are in A001631.
%Y Cf. A008287 (quadrinomial coefficients) and A073817 (tetranacci with different initial conditions).
%K nonn,easy,nice
%O 0,6
%A _N. J. A. Sloane_
%E Definition augmented (with 4 initial terms) by _Daniel Forgues_, Dec 02 2009
%E Deleted certain dangerous or potentially dangerous links. - _N. J. A. Sloane_, Jan 30 2021
|
