%I M0795 N0301 #108 Jun 25 2024 08:32:19
%S 0,0,1,2,3,6,12,23,44,85,164,316,609,1174,2263,4362,8408,16207,31240,
%T 60217,116072,223736,431265,831290,1602363,3088654,5953572,11475879,
%U 22120468,42638573,82188492,158423412,305370945,588621422,1134604271,2187020050
%N 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.
%C Also (with a different offset), coordination sequence for (4,infinity,infinity) tiling of hyperbolic plane. - _N. J. A. Sloane_, Dec 29 2015
%C Apparently for n>=2 the number of 1-D walks of length n-2 using steps +1, +3 and -1, avoiding consecutive -1 steps. - _David Scambler_, Jul 15 2013
%C From Elkhan Aday and _Greg Dresden_, Jun 24 2024: (Start)
%C For n > 1, a(n) is the number of ways to tile a skew double-strip of n-1 cells with one extra initial cell, using squares and all possible "dominoes". Here is the skew double-strip corresponding to n=12, with 11 cells:
%C ___ ___ ___ ___ ___
%C | | | | | |
%C ___ _|___|___|___|___|___|
%C | | | | | | |
%C |___|___|___|___|___|___|,
%C and here are the three possible "domino" tiles:
%C ___ ___
%C | | | |
%C _| _| |_ |_ _______
%C | | | | | |
%C |___|, |___|, |_______|.
%C As an example, here is one of the a(12) = 609 ways to tile the skew double-strip of 11 cells:
%C ___ _______ _______
%C | | | | | |
%C _____|_ |___|_ _|_ _| _|
%C | | | | | |
%C |_______|___|___|___|___|. (End)
%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="/A001630/b001630.txt">Table of n, a(n) for n = 0..3503</a> (terms 0..500 from T. D. Noe)
%H Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, <a href="http://www.emis.de/journals/JIS/VOL18/Szczyrba/sz3.pdf">Analytic Representations of the n-anacci Constants and Generalizations Thereof</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
%H J. W. Cannon and P. Wagreich, <a href="http://dx.doi.org/10.1007/BF01444714">Growth functions of surface groups</a>, Mathematische Annalen, 1992, Volume 293, pp. 239-257. See Prop. 3.1.
%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), pp. 6ff.
%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 Helmut 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. Int. Seq. 17 (2014) # 14.6.2, even length, r=3.
%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^2*(1+x)/(-1+x+x^2+x^3+x^4). [_Simon Plouffe_ in his 1992 dissertation]
%F a(n) = A000078(n) + A000078(n+1) = a(n-1) + A000078(n+1) - A000078(n-1). - _Henry Bottomley_
%F a(n) = 2*a(n-1) - a(n-5) with n>4, a(0)=a(1)=0, a(2)=1, a(3)=2, a(4)=3. - _Vincenzo Librandi_, Dec 21 2010
%F G.f.: x^2 + x^3*G(0) where G(k) = 2 + x*(1 + x + x^2 + (1+x)*(1+x^2)*G(k+1)). - _Sergei N. Gladkovskii_, Jan 27 2013 [Edited by _Michael Somos_, Nov 12 2013]
%e G.f. = x^2 + 2*x^3 + 3*x^4 + 6*x^5 + 12*x^6 + 23*x^7 + 44*x^8 + 85*x^9 + ...
%p a:= proc(n) option operator; local M; M := Matrix(4, (i,j)-> if (i=j-1) or j=1 then 1 else 0 fi)^n; M[1,4]+M[1,3] end; seq (a(n), n=0..34); # _Alois P. Heinz_, Aug 01 2008
%t a=0; b=0; c=1; d=2; lst={a, b, c, d}; Do[e=a+b+c+d; AppendTo[lst, e]; a=b; b=c; c=d; d=e, {n, 4!}]; lst (* _Vladimir Joseph Stephan Orlovsky_, Sep 30 2008 *)
%t RecurrenceTable[{a[0] == a[1] == 0, a[2] == 1, a[3] == 2, a[n] == a[n - 1] + a[n - 2] + a[n - 3] + a[n - 4]}, a, {n, 35}] (* or *) a = {0, 0, 1, 2}; Do[AppendTo[a, a[[-1]] + a[[-2]] + a[[-3]] + a[[-4]]], {35}]; a (* _Bruno Berselli_, Jan 29 2013 *)
%t CoefficientList[Series[- x^2 * (1 + x)/(- 1 + x + x^2 + x^3 + x^4), {x, 0, 35}], x] (* _Vincenzo Librandi_, Jan 29 2013 *)
%t LinearRecurrence[{1,1,1,1},{0,0,1,2},40] (* _Harvey P. Dale_, Aug 25 2013 *)
%o (Magma) I:=[0, 0, 1, 2]; [n le 4 select I[n] else Self(n-1)+ Self(n-2) + Self(n-3) + Self(n-4): n in [1..40]]; // _Vincenzo Librandi_, Jan 29 2013
%o (PARI) concat([0, 0], Vec(-x^2*(1+x)/(-1+x+x^2+x^3+x^4) + O(x^50))) \\ _Michel Marcus_, Dec 30 2015
%Y Coordination sequences for triangular tilings of hyperbolic space: A001630, A007283, A054886, A078042, A096231, A163876, A179070, A265057, A265058, A265059, A265060, A265061, A265062, A265063, A265064, A265065, A265066, A265067, A265068, A265069, A265070, A265071, A265072, A265073, A265074, A265075, A265076, A265077.
%Y Cf. A000032.
%K nonn,easy
%O 0,4
%A _N. J. A. Sloane_