A356807 Tetranacci sequence beginning with 3, 7, 12, 24.

3, 7, 12, 24, 46, 89, 171, 330, 636, 1226, 2363, 4555, 8780, 16924, 32622, 62881, 121207, 233634, 450344, 868066, 1673251, 3225295, 6216956, 11983568, 23099070, 44524889, 85824483, 165432010, 318880452, 614661834, 1184798779, 2283773075, 4402114140, 8485347828

Offset: 1

Author

Greg Dresden and Hangyu Liang, Aug 29 2022

Keywords

• nonn
• easy

Comments

By "Tetranacci sequence" we mean a sequence in which each term is the sum of the four previous terms.

For n>1, a(n) is the number of ways to tile this figure of length n with squares, dominoes, trominoes, and tetraminoes:

_

|||_________ _

|||_|||_|| ... ||

Examples

			Here is one of the a(6) = 89 ways to tile this figure of length 6 with tiles of length <= 4, this one using three squares, one domino, and one tromino:
   ___
  | |_|_______
  |_|_____|_|_|
		

Links

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

Crossrefs

Cf. A022120, A100683.

Programs

Mathematica

LinearRecurrence[{1, 1, 1, 1}, {3, 7, 12, 24}, 50] (* Paolo Xausa, Aug 30 2024 *)

Formula

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

a(n) = 5*b(n+2) + 2*b(n+1) - 2*b(n-2) for b(n) = A000078(n) the tetranacci numbers.

a(n) = L(n+2) - F(n-2) + Sum_{k=0..n-3} a(k)*F(n-k-1), for L(n) and F(n) the Lucas and Fibonacci numbers.

G.f.: x*(-2*x^3 - 2*x^2 - 4*x - 3)/(x^4 + x^3 + x^2 + x - 1). - Chai Wah Wu, Aug 30 2022