A354080 a(n) = a(n-1) + a(n-2) + a(n-3), with a(0)=1, a(1)=4, a(2)=5.

1, 4, 5, 10, 19, 34, 63, 116, 213, 392, 721, 1326, 2439, 4486, 8251, 15176, 27913, 51340, 94429, 173682, 319451, 587562, 1080695, 1987708, 3655965, 6724368, 12368041, 22748374, 41840783, 76957198, 141546355

Offset: 0

Author

Greg Dresden and Veda Garigipati, Jul 13 2022

Keywords

• nonn
• easy

Comments

a(n) is the number of ways to tile this T-shaped figure of length n with squares, dominoes, and trominoes. Shown here is the figure for n=9.

_

||______________

|||_|||_|||_|

|_|

Examples

			Here is one of the a(9)=392 tilings, this one with four squares, two dominoes, and one tromino.
   _
  |_|_______________
  | |_|_____|_|_|___|
  |_|
		

Links

• Paolo Xausa, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (1,1,1).

Crossrefs

Cf. A000032, A000045, A000073.

Programs

Mathematica

LinearRecurrence[{1, 1, 1}, {1, 4, 5}, 50] (* Paolo Xausa, May 27 2024 *)

Formula

a(n) = T(n+2) + 3*T(n+1), for T(n) = A000073(n) the tribonacci numbers.

a(n) = L(n+1) + F(n) + Sum_{i=1.. n-2} F(i)*a(n-2-i), for F(n) = A000045(n) the Fibonacci numbers and L(n) = A000032(n) the Lucas numbers.

a(n) = L(n+1) + T(n+1) + Sum_{i=1.. n-2} L(i)*T(n-i), for L(n) = A000032(n) the Lucas numbers and T(n) = A000073(n) the tribonacci numbers.

G.f.: (1 + 3*x)/(1 - x - x^2 - x^3). - Stefano Spezia, Jul 14 2022