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

0, 1, 1, 4, 8, 21, 49, 120, 288, 697, 1681, 4060, 9800, 23661, 57121, 137904, 332928, 803761, 1940449, 4684660, 11309768, 27304197, 65918161, 159140520, 384199200, 927538921, 2239277041, 5406093004, 13051463048, 31509019101, 76069501249, 183648021600

Offset: 0

Author

Paul Barry, Jul 22 2004

Keywords

• easy
• nonn

Comments

Counts walks of length n between two vertices of a triangle, when a loop has been added at the third vertex.

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

Starting (1, 1, 4, 8, 21, ...) = row sums of triangle A157898. - Gary W. Adamson, Mar 08 2009

Convolution of Pell(n) = A000129(n) and (-1)^n. - Paul Barry, Oct 22 2009

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

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

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.
• Mark Shattuck, Combinatorial Proofs of Some Formulas for Triangular Tilings, Journal of Integer Sequences, 17 (2014), #14.5.5.
• Index entries for linear recurrences with constant coefficients, signature (1,3,1).

Crossrefs

Cf. A000129, A001333, A051927, A097075, A110048, A157898, A375726.

Programs

Magma

[(Evaluate(DicksonFirst(n,-1), 2) -2*(-1)^n)/4: n in [0..40]]; // G. C. Greubel, Aug 18 2022

Mathematica

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 *)

SageMath

[(lucas_number2(n,2,-1) -2*(-1)^n)/4 for n in (0..40)] # G. C. Greubel, Aug 18 2022

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). [corrected by Paul Curtz, Mar 04 2008]

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

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

a(n) = Sum_{k=0..n} (-1)^k*Pell(n-k). - Paul Barry, Oct 22 2009

From R. J. Mathar, Jul 06 2011: (Start)

G.f.: x / ( (1+x)*(1-2*x-x^2) ).

a(n) + a(n+1) = A000129(n+1). (End)

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