%I #59 Sep 20 2024 06:29:01
%S 0,1,1,4,8,21,49,120,288,697,1681,4060,9800,23661,57121,137904,332928,
%T 803761,1940449,4684660,11309768,27304197,65918161,159140520,
%U 384199200,927538921,2239277041,5406093004,13051463048,31509019101,76069501249,183648021600
%N Expansion of g.f. x/(1 - x - 3*x^2 - x^3).
%C Counts walks of length n between two vertices of a triangle, when a loop has been added at the third vertex.
%C a(n) is the center term of the 3 X 3 matrix [0,1,0; 0,0,1; 1,3,1]^n. - _Gary W. Adamson_, May 30 2008
%C Starting (1, 1, 4, 8, 21, ...) = row sums of triangle A157898. - _Gary W. Adamson_, Mar 08 2009
%C Convolution of Pell(n) = A000129(n) and (-1)^n. - _Paul Barry_, Oct 22 2009
%C a(n+1) is the number of ways to choose points on a 2 X n lattice eliminating the upper left and lower right corners such that the points are not adjacent to each other. (See A375726 for proof) - _Yifan Xie_, Aug 25 2024
%C a(n+1) is the number of compositions (ordered partitions) of n into parts 1, 2, and 3 where there are three kinds of part 2. - _Joerg Arndt_, Aug 27 2024
%H G. C. Greubel, <a href="/A097076/b097076.txt">Table of n, a(n) for n = 0..1000</a>
%H J. Bodeen, S. Butler, T. Kim, X. Sun and S. Wang, <a href="https://doi.org/10.37236/3478">Tiling a strip with triangles</a>, El. J. Combinat. 21 (1) (2014) P1.7.
%H Mark Shattuck, <a href="https://www.emis.de/journals/JIS/VOL17/Shattuck/shattuck8.html">Combinatorial Proofs of Some Formulas for Triangular Tilings</a>, Journal of Integer Sequences, 17 (2014), #14.5.5.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,3,1).
%F a(n) = ( (1+sqrt(2))^n + (1-sqrt(2))^n - 2*(-1)^n )/4.
%F a(n) = a(n-1) + 3*a(n-2) + a(n-3). [corrected by _Paul Curtz_, Mar 04 2008]
%F a(n) = (Sum_{k=0..floor(n/2)} binomial(n, 2*k)*2^k)/2 - (-1)^n/2.
%F a(n) = (A001333(n) - (-1)^n)/2.
%F a(n) = Sum_{k=0..n} (-1)^k*Pell(n-k). - _Paul Barry_, Oct 22 2009
%F From _R. J. Mathar_, Jul 06 2011: (Start)
%F G.f.: x / ( (1+x)*(1-2*x-x^2) ).
%F a(n) + a(n+1) = A000129(n+1). (End)
%F E.g.f.: (exp(x)*cosh(sqrt(2)*x) - cosh(x) + sinh(x))/2. - _Stefano Spezia_, Mar 31 2024
%t CoefficientList[Series[x/(1-x-3x^2-x^3),{x,0,40}],x] (* or *) LinearRecurrence[{1,3,1},{0,1,1},40] (* _Vladimir Joseph Stephan Orlovsky_, Jan 30 2012 *)
%o (Magma) [(Evaluate(DicksonFirst(n,-1), 2) -2*(-1)^n)/4: n in [0..40]]; // _G. C. Greubel_, Aug 18 2022
%o (SageMath) [(lucas_number2(n,2,-1) -2*(-1)^n)/4 for n in (0..40)] # _G. C. Greubel_, Aug 18 2022
%Y Cf. A000129, A001333, A051927, A097075, A110048, A157898, A375726.
%K easy,nonn
%O 0,4
%A _Paul Barry_, Jul 22 2004