A001631 - OEIS

%I M1081 N0410 #119 Jan 05 2025 19:51:32

%S 0,0,1,0,1,2,4,7,14,27,52,100,193,372,717,1382,2664,5135,9898,19079,

%T 36776,70888,136641,263384,507689,978602,1886316,3635991,7008598,

%U 13509507,26040412,50194508,96753025,186497452,359485397,692930382,1335666256,2574579487

%N 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 The "standard" tetranacci numbers with initial terms (0,0,0,1) are listed in A000078.

%C 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 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 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    ___ ___ ___ ___ ___ ___

%C   |   |   |   |   |   |   |

%C  _|___|___|___|___|_ _|___|

%C |   |   |   |   |   |   |

%C |___|___|___|___|___|___|,

%C and here are the three possible "domino" tiles:

%C    ___     ___

%C   |   |   |   |

%C  _|  _|   |_  |_      _______

%C |   |       |   |    |       |

%C |___|,      |___|,   |_______|. - _Greg Dresden_ and Ruotong Li, Jun 05 2024

%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 Harvey P. Dale, <a href="/A001631/b001631.txt">Table of n, a(n) for n = 0..1000</a>

%H 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 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 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 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 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,1).

%F G.f.: ((x-1)*x^2)/(x^4+x^3+x^2+x-1). - _Harvey P. Dale_, Oct 21 2011

%p A001631:=(-1+z)/(-1+z+z**2+z**3+z**4); # conjectured by _Simon Plouffe_ in his 1992 dissertation

%p 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 LinearRecurrence[{1, 1, 1, 1}, {0, 0, 1, 0}, 100] (* _Vladimir Joseph Stephan Orlovsky_, Jul 01 2011 *)

%t 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 (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 (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 (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 Absolute values of first differences of standard tetranacci numbers A000078.

%Y Cf. A000288 (variant: starting with 1, 1, 1, 1).

%Y Cf. A000336 (variant: sum replaced by product).

%K nonn,easy

%O 0,6

%A _N. J. A. Sloane_

%E More terms from Larry Reeves (larryr(AT)acm.org), Jul 31 2000

%E Edited by _M. F. Hasler_, Apr 20 2018