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

Offset

1,1

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:

___

|_|_|_________ _

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

Links

Table of n, a(n) for n=1..30.

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

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

Example

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:
   ___
  | |_|_______
  |_|_____|_|_|

Crossrefs

Cf. A022120, A100683.

Sequence in context: A262567 A226229 A167491 * A210185 A280345 A062325

Adjacent sequences: A356804 A356805 A356806 * A356808 A356809 A356810

Keyword

nonn,easy

Author

Greg Dresden and Hangyu Liang, Aug 29 2022

Status

approved