A097075 Expansion of g.f. (1-x-x^2)/(1-x-3*x^2-x^3).

1, 0, 2, 3, 9, 20, 50, 119, 289, 696, 1682, 4059, 9801, 23660, 57122, 137903, 332929, 803760, 1940450, 4684659, 11309769, 27304196, 65918162, 159140519, 384199201, 927538920, 2239277042, 5406093003, 13051463049, 31509019100, 76069501250

Offset

0,3

Comments

Counts closed walks of length n at a vertex of a triangle, to which a loop has been added at one of the other vertices.

a(n) is the top left entry of the n-th power of the 3 X 3 matrix [0, 1, 1; 1, 1, 1; 1, 1, 0] or of the 3 X 3 matrix [0, 1, 1; 1, 0, 1; 1, 1, 1].

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

J. Bodeen, S. Butler, T. Kim, X. Sun, and S. Wang, Tiling a strip with triangles, El. J. Combinat. 21 (1) (2014) P1.7.

Index entries for linear recurrences with constant coefficients, signature (1,3,1).

Formula

a(n) = ((1+sqrt(2))^n + (1-sqrt(2))^n + 2*(-1)^n)/4.

a(n) = a(n-1) + 3*a(n-2) + a(n-3).

a(n) = (1/2)*((-1)^n + Sum_{k=0..floor(n/2)} binomial(n, 2*k)*2^k).

a(n) = ((-1)^n + A001333(n))/2.

E.g.f.: (cosh(x) + exp(x)*cosh(sqrt(2)*x) - sinh(x))/2. - Stefano Spezia, Mar 31 2024

Mathematica

LinearRecurrence[{1, 3, 1}, {1, 0, 2}, 41] (* or *) Table[(LucasL[n, 2] +2*(-1)^n)/4, {n, 0, 40}] (* G. C. Greubel, Aug 18 2022 *)

Prog

(PARI) Vec((1-x-x^2)/(1-x-3*x^2-x^3) + O(x^50)) \\ Michel Marcus, Mar 25 2014
(Magma) [(Evaluate(DicksonFirst(n, -1), 2) +2*(-1)^n)/4: n in [0..40]]; // G. C. Greubel, Aug 18 2022
(SageMath) [(lucas_number2(n, 2, -1) +2*(-1)^n)/4 for n in (0..40)] # G. C. Greubel, Aug 18 2022

Crossrefs

Cf. A000129, A001333, A051927, A097076.

Sequence in context: A231368 A369517 A245123 * A036673 A111189 A001004

Adjacent sequences: A097072 A097073 A097074 * A097076 A097077 A097078

Keyword

easy,nonn

Author

Paul Barry, Jul 22 2004

Status

approved