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

Author

Greg Dresden and Ziyao Geng, Jul 02 2021

Keywords

• nonn
• easy

Examples

			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.
  ._________.  ._________.  ._________.
  | | |___| |  |  ___|___|  | |___|___|
  | |_|___|_|  | | |___| |  | |___|___|
  |_____|___|  |_|_|___|_|  |_____|___|
		

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).

Crossrefs

Cf. A052980.

Programs

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

Mathematica

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

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

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).

Extensions

Corrected by Greg Dresden, Sep 04 2021