cp's OEIS Frontend

A001631 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).

%I A001631 M1081 N0410 #119 Jan 05 2025 19:51:32
%S A001631 0,0,1,0,1,2,4,7,14,27,52,100,193,372,717,1382,2664,5135,9898,19079,
%T A001631 36776,70888,136641,263384,507689,978602,1886316,3635991,7008598,
%U A001631 13509507,26040412,50194508,96753025,186497452,359485397,692930382,1335666256,2574579487
%N A001631 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).
%C A001631 The "standard" tetranacci numbers with initial terms (0,0,0,1) are listed in A000078.
%C A001631 Starting (1, 2, 4, ...) is the INVERT transform of the cyclic sequence (1, 1, 1, 0, (repeat) ...); equivalent to the statement that (1, 2, 4, ...) corresponding to n = (1, 2, 3, ...) represents the numbers of ordered compositions of n using terms in the set "not multiples of four". - _Gary W. Adamson_, May 13 2013
%C A001631 a(n+4) equals the number of n-length binary words avoiding runs of zeros of lengths 4i+3, (i=0,1,2,...). - _Milan Janjic_, Feb 26 2015
%C A001631 a(n) is the number of ways to tile a skew double-strip of n-2 cells using squares and all possible "dominos", as seen in the comments in A000078, but with the added provision that the first tile (in the lower left corner) must be a domino. For reference, here is the skew double-strip corresponding to n=14, with 12 cells:
%C A001631    ___ ___ ___ ___ ___ ___
%C A001631   |   |   |   |   |   |   |
%C A001631  _|___|___|___|___|_ _|___|
%C A001631 |   |   |   |   |   |   |
%C A001631 |___|___|___|___|___|___|,
%C A001631 and here are the three possible "domino" tiles:
%C A001631    ___     ___
%C A001631   |   |   |   |
%C A001631  _|  _|   |_  |_      _______
%C A001631 |   |       |   |    |       |
%C A001631 |___|,      |___|,   |_______|. - _Greg Dresden_ and Ruotong Li, Jun 05 2024
%D A001631 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001631 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001631 Harvey P. Dale, <a href="/A001631/b001631.txt">Table of n, a(n) for n = 0..1000</a>
%H A001631 Matthias Beck and Neville Robbins, <a href="http://arxiv.org/abs/1403.0665">Variations on a Generating Function Theme: Enumerating Compositions with Parts Avoiding an Arithmetic Sequence</a>, arXiv:1403.0665 [math.NT], 2014.
%H A001631 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>, Journal of Integer Sequences, 19 (2016), #16.8.2.
%H A001631 W. C. Lynch, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/8-1/lynch.pdf">The t-Fibonacci numbers and polyphase sorting</a>, Fib. Quart., 8 (1970), pp. 6-22.
%H A001631 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 A001631 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A001631 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,1).
%F A001631 G.f.: ((x-1)*x^2)/(x^4+x^3+x^2+x-1). - _Harvey P. Dale_, Oct 21 2011
%p A001631 A001631:=(-1+z)/(-1+z+z**2+z**3+z**4); # conjectured by _Simon Plouffe_ in his 1992 dissertation
%p A001631 a:= n-> (Matrix([[0,-1,2,-1]]). Matrix(4, (i,j)-> `if`(i=j-1 or j=1, 1, 0))^n)[1,1]: seq(a(n), n=0..35); # _Alois P. Heinz_, Aug 01 2008
%t A001631 LinearRecurrence[{1, 1, 1, 1}, {0, 0, 1, 0}, 100] (* _Vladimir Joseph Stephan Orlovsky_, Jul 01 2011 *)
%t A001631 CoefficientList[Series[((-1+x) x^2)/(-1+x+x^2+x^3+x^4),{x,0,50}],x] (* _Harvey P. Dale_, Oct 21 2011 *)
%o A001631 (PARI) a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 1,1,1,1]^n)[1,3] \\ _Charles R Greathouse IV_, Apr 08 2016, simplified by _M. F. Hasler_, Apr 20 2018
%o A001631 (PARI) x='x+O('x^30); concat([0,0], Vec(((x-1)*x^2)/(x^4+x^3+x^2+x-1))) \\ _G. C. Greubel_, Jan 09 2018
%o A001631 (Magma) I:=[0,0,1,0]; [n le 4 select I[n] else Self(n-1) + Self(n-2) + Self(n-3) + Self(n-4): n in [1..30]]; // _G. C. Greubel_, Jan 09 2018
%Y A001631 Absolute values of first differences of standard tetranacci numbers A000078.
%Y A001631 Cf. A000288 (variant: starting with 1, 1, 1, 1).
%Y A001631 Cf. A000336 (variant: sum replaced by product).
%K A001631 nonn,easy
%O A001631 0,6
%A A001631 _N. J. A. Sloane_
%E A001631 More terms from Larry Reeves (larryr(AT)acm.org), Jul 31 2000
%E A001631 Edited by _M. F. Hasler_, Apr 20 2018