A374729 Number of tilings using squares, dominos, and flexible trominos of a strip of length n-1 and with an n-th cell placed on top of the middle of the strip.

0, 1, 2, 4, 7, 12, 21, 40, 76, 139, 254, 466, 855, 1576, 2905, 5340, 9816, 18053, 33202, 61076, 112351, 206636, 380045, 699012, 1285684, 2364759, 4349502, 7999954, 14714159, 27063568, 49777681, 91555464, 168396816, 309729961, 569682082, 1047808756

Offset

0,3

Comments

As an illustration, here are the figures for n=8 and n=9, respectively.

_ _

_____|_|_____ _______|_|_____

|_|_|_|_|_|_|_|, |_|_|_|_|_|_|_|_|.

Links

Table of n, a(n) for n=0..35.

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

Formula

a(n) = a(n-1) + 2*a(n-3) + 2*a(n-5) + 2*a(n-6) - a(n-8) - a(n-9).

a(2*n) = a(2*n-1) + a(2*n-3) + a(2*n-4) + 3*a(2*n-5) + 2*a(2*n-6) + a(2*n-7).

a(2*n) = A000073(2*n+1) + A000073(n+1)*(A000073(n+1) + 2*A000073(n)).

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

a(2*n+1) = A000073(2*n+2) + A000073(n+1)^2 + A000073(n+2)*(A000073(n+1) + A000073(n)).

G.f.: x*(1 + x + 2*x^2 + x^3 + x^4 - x^5 - x^6)/(1 - x - 2*x^3 - 2*x^5 -

2*x^6 + x^8 + x^9).

Example

For n=8, here is one of a(8)=76 possible tilings with squares, dominos, and flexible trominos.
       _
 _____| |_____
|___|_|___|___|.

Mathematica

LinearRecurrence[{1, 0, 2, 0, 2, 2, 0, -1, -1}, {0, 1, 2, 4, 7, 12, 21, 40, 76}, 40]

Crossrefs

Cf. A000073.

Sequence in context: A005126 A054151 A018176 * A372540 A135460 A274174

Adjacent sequences: A374726 A374727 A374728 * A374730 A374731 A374732

Keyword

nonn,easy

Author

Greg Dresden and Yinuo Zhu, Jul 17 2024

Status

approved