A353879 Number of tilings of a 4 X n rectangle using right trominoes, dominoes and 1 X 1 tiles.

1, 5, 189, 3633, 83374, 1817897, 40220893, 886130549, 19546906987, 431024540644, 9505433227293, 209617856008535, 4622624792880217, 101940750143038657, 2248057208102711472, 49575464007447758483, 1093267021618939507743, 24109360928450426884813, 531673668551361276666101

Offset

0,2

Comments

For tiling algorithm see A351322.

Links

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

Index entries for linear recurrences with constant coefficients, signature (14,183,-37,-1929,2419,-212,-333,25,15).

Formula

G.f.: (1 - 9*x - 64*x^2 + 109*x^3 + 39*x^4 + 41*x^5 + 12*x^6 - 7*x^7 - 2*x^8) / (1 - 14*x - 183*x^2 + 37*x^3 + 1929*x^4 - 2419*x^5 + 212*x^6 + 333*x^7 - 25*x^8-15*x^9).

a(n) = 14*a(n-1) + 183*a(n-2) - 37*a(n-3) - 1929*a(n-4) + 2419*a(n-5) - 212*a(n-6) - 333*a(n-7) + 25*a(n-8) + 15*a(n-9).

Example

a(2)=189.
The number of tilings (mirroring included) using r trominoes
      ___   ___   ___   ___
r=1: |  _| |  _| | |_| |_2_|    r=0: 71 = A030186(4)
     |_|_| |_| | |___| |_  |
     | 7 | |3|_| | 7 | |3|_|
     |___| |___| |___| |___|
      4*7 + 4*3 + 4*7 + 4*6 = 92
      ___   ___   ___   ___   ___   ___   ___
r=2: |  _| |  _| |  _| |  _| |  _| | |_| | |_|
     |_| | |_|2| |_|_| |_|_| |_|_| |___| |___|
     |___| | |_| |  _|_|_| | |_  | |_  | |  _|
     |_2_| |___| |_|_| |___| |_|_| |_|_| |_|_|
      4*2 + 2*2 + 4*1 + 2*1 + 4*1 + 2*1 + 2*1 = 26
Result: a(2) = 71+92+26 = 189.
Legend:
   ___              ___      ___
  |_2_| stands for |___| or |_|_|
     _                _        _        _
   _|3|             _| |     _|_|     _|_|
  |___| stands for |_|_| or |___| or |_|_|
   ___              ___   ___   ___   ___   ___   ___      ___
  | 7 |            |___| |_|_| |___| | | | |_| | | |_|    |_|_|
  |___| stands for |___|,|___|,|_|_|,|_|_|,|_|_|,|_|_| or |_|_|

Prog

(Maxima) See A352589.

Crossrefs

Cf. A030186, A127870, A165791, A351322, A352589, A353877, A353878.

Sequence in context: A268001 A096543 A209412 * A138733 A222363 A316330

Adjacent sequences: A353876 A353877 A353878 * A353880 A353881 A353882

Keyword

nonn,easy

Author

Gerhard Kirchner, May 09 2022

Status

approved