login
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
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.
_ _
_____|_|_____ _______|_|_____
|_|_|_|_|_|_|_|, |_|_|_|_|_|_|_|_|.
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
KEYWORD
nonn,easy
AUTHOR
Greg Dresden and Yinuo Zhu, Jul 17 2024
STATUS
approved