A346054 Number of ways to tile a 3 X n strip with dominoes and L-shaped 5-minoes.

1, 0, 3, 8, 13, 52, 119, 308, 873, 2184, 5867, 15552, 40581, 107836, 283871, 748076, 1976545, 5208784, 13743315, 36260088, 95627773, 252289476, 665499975, 1755466916, 4630903129, 12215645848, 32223689915, 85003275440, 224228961909, 591494654412, 1560303157679

Offset

0,3

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Greg Dresden and Michael Tulskikh, Tilings of 2 X n boards with dominos and L-shaped trominos, Journal of Integer Sequences 24 (2021), article 21.4.5.

Index entries for linear recurrences with constant coefficients, signature (1,3,5,-4).

Formula

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

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

Example

Here are two such tilings for a 3 X 3 strip; each has four rotations thus demonstrating that a(3)=8.
  ._____.  ._____.
  | | | |  | |___|
  | |_|_|  | |___|
  |_____|  |_____|
For a 3 X 4 strip, here are three of the possible a(4)=13 tilings.
  ._______.  ._______.  ._______.
  | |___  |  |  ___| |  |___|___|
  | |___| |  | |___| |  | |___| |
  |_____|_|  |_|_____|  |_|___|_|
For a 3 X 5 strip, here are three of the possible a(5)=52 tilings.
  ._________.  ._________.  ._________.
  | | |___| |  |  ___|___|  | |___|___|
  | |_|___|_|  | | |___| |  | |___|___|
  |_____|___|  |_|_|___|_|  |_____|___|

Mathematica

LinearRecurrence[{1, 3, 5, -4}, {1, 0, 3, 8}, 50];

Prog

(Magma) I:=[1, 0, 3, 8]; [n le 4 select I[n] else Self(n-1) +3*Self(n-2) +5*Self(n-3) -4*Self(n-4): n in [1..50]]; // G. C. Greubel, Dec 01 2022
(SageMath)
@CachedFunction
def a(n): # a = A346054
    if (n<4): return (1, 0, 3, 8)[n]
    else: return a(n-1) + 3*a(n-2) + 5*a(n-3) - 4*a(n-4)
[a(n) for n in range(51)] # G. C. Greubel, Dec 01 2022

Crossrefs

Cf. A052980.

Sequence in context: A355240 A355514 A281267 * A153891 A056402 A366071

Adjacent sequences: A346051 A346052 A346053 * A346055 A346056 A346057

Keyword

nonn,easy

Author

Greg Dresden and Ziyao Geng, Jul 02 2021

Extensions

Corrected by Greg Dresden, Sep 04 2021

Status

approved