A165791 -id:A165791 - cp's OEIS frontend

A219987 Number A(n,k) of tilings of a k X n rectangle using dominoes and right trominoes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 2, 0, 1, 1, 1, 5, 5, 1, 1, 1, 0, 11, 8, 11, 0, 1, 1, 1, 24, 55, 55, 24, 1, 1, 1, 0, 53, 140, 380, 140, 53, 0, 1, 1, 1, 117, 633, 2319, 2319, 633, 117, 1, 1, 1, 0, 258, 1984, 15171, 21272, 15171, 1984, 258, 0, 1

Offset: 0

Alois P. Heinz, Dec 02 2012

			A(3,3) = 8, because there are 8 tilings of a 3 X 3 rectangle using dominoes and right trominoes:
  .___._.   .___._.   .___._.   .___._.
  |___| |   |___| |   |___| |   |_. | |
  | ._|_|   | | |_|   | |___|   | |_|_|
  |_|___|   |_|___|   |_|___|   |_|___|
  ._.___.   ._.___.   ._.___.   ._.___.
  | |___|   | | ._|   | |___|   | |___|
  |___| |   |_|_| |   |_|_. |   |_| | |
  |___|_|   |___|_|   |___|_|   |___|_|
Square array A(n,k) begins:
  1,  1,   1,    1,     1,       1,         1,          1, ...
  1,  0,   1,    0,     1,       0,         1,          0, ...
  1,  1,   2,    5,    11,      24,        53,        117, ...
  1,  0,   5,    8,    55,     140,       633,       1984, ...
  1,  1,  11,   55,   380,    2319,     15171,      96139, ...
  1,  0,  24,  140,  2319,   21272,    262191,    2746048, ...
  1,  1,  53,  633, 15171,  262191,   5350806,  100578811, ...
  1,  0, 117, 1984, 96139, 2746048, 100578811, 3238675344, ...

Liang Kai, Antidiagonals n = 0..35, flattened (Antidiagonals n = 0..31 from Alois P. Heinz)
Kai Liang, Solving tiling enumeration problems by tensor network contractions, arXiv:2503.17698 [math.CO], 2025. See p. 25, Table 4.
Wikipedia, Domino
Wikipedia, Tromino

Columns (or rows) k=0-10 give: A000012, A059841, A052980, A165716, A165791, A219988, A219989, A219990, A219991, A219992, A219993.
Main diagonal gives: A219994.
Cf. A219866, A364457.

b:= proc(n, l) option remember; local k, t;
      if max(l[])>n then 0 elif n=0 or l=[] then 1
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
    else for k do if l[k]=0 then break fi od;
         b(n, subsop(k=2, l))+
         `if`(k>1 and l[k-1]=1, b(n, subsop(k=2, k-1=2, l)), 0)+
         `if`(k `if`(n>=k, b(n, [0$k]), b(k, [0$n])):
seq(seq(A(n, d-n), n=0..d), d=0..14);

b[n_, l_] := b[n, l] = Module[{k, t}, If[Max[l] > n, 0, If[n == 0 || l == {}, 1, If[Min[l] > 0, t = Min[l]; b[n-t, l-t], For[k = 1, True, k++, If[l[[k]] == 0, Break[]]]; b[n, ReplacePart[l, k -> 2]] + If[k > 1 && l[[k-1]] == 1, b[n, ReplacePart[l, {k -> 2, k-1 -> 2}]], 0] + If[k < Length[l] && l[[k+1]] == 1, b[n, ReplacePart[l, {k -> 2, k+1 -> 2}]], 0] + If[k < Length[l] && l[[k+1]] == 0, b[n, ReplacePart[l, {k -> 1, k+1 -> 1}]] + b[n, ReplacePart[l, {k -> 1, k+1 -> 2}]] + b[n, ReplacePart[l, {k -> 2, k+1 -> 1}]], 0] + If[k+1 < Length[l] && l[[k+1]] == 0 && l[[k+2]] == 0, b[n, ReplacePart[l, {k -> 2, k+1 -> 2, k+2 -> 2}]] + b[n, ReplacePart[l, {k -> 2, k+1 -> 2, k+2 -> 1}]], 0]]]]]; a[n_, k_] := If[n >= k, b[n, Array[0&, k]], b[k, Array[0&, n]]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 05 2013, translated from Alois P. Heinz's Maple program *)

from sage.combinat.tiling import TilingSolver, Polyomino
def A(n,k):
    p = Polyomino([(0,0), (0,1)])
    q = Polyomino([(0,0), (0,1), (1,0)])
    T = TilingSolver([p,q], box=[n,k], reusable=True, reflection=True)
    return T.number_of_solutions()
# Ralf Stephan, May 21 2014

A226322 Number of tilings of a 4 X n rectangle using L tetrominoes and 2 X 2 tiles.

Original entry on oeis.org

1, 0, 3, 6, 19, 48, 141, 378, 1063, 2920, 8115, 22418, 62123, 171876, 475919, 1317250, 3646681, 10094356, 27943739, 77353070, 214129845, 592752572, 1640859689, 4542223926, 12573787053, 34806745800, 96352029241, 266721635838, 738338745535, 2043868995512

Offset: 0

Alois P. Heinz, Jun 03 2013

			a(3) = 6:
._____.  ._____.  .___._.  ._.___.  ._____.  ._____.
| .___|  |___. |  |   | |  | |   |  |___. |  | .___|
|_|_. |  | ._|_|  |___| |  | |___|  |   |_|  |_|   |
|   | |  | |   |  | |___|  |___| |  |___| |  | |___|
|___|_|  |_|___|  |_____|  |_____|  |_____|  |_____|

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Nicolas Bělohoubek and Antonín Slavík, L-Tetromino Tilings and Two-Color Integer Compositions, Univ. Karlova (Czechia, 2025). See p. 10.
Index entries for linear recurrences with constant coefficients, signature (0,5,6,4,0,-1,0,-3,-2,-4,0,-2).

Cf. A054854, A054856, A084480, A165716, A165791, A165799, A174248, A232497, A233191, A233266.

a:= n-> (Matrix(12, (i, j)-> `if`(i+1=j, 1, `if`(i=12,
    [-2, 0, -4, -2, -3, 0, -1, 0, 4, 6, 5, 0][j], 0)))^(n+8).
    <<-1, 0, 1/2, [0$5][], 1, 0, 3, 6>>)[1, 1]:
seq(a(n), n=0..40);

a[n_] := MatrixPower[ Table[ If[i+1 == j, 1, If[i == 12, {-2, 0, -4, -2, -3, 0, -1, 0, 4, 6, 5, 0}[[j]], 0]], {i, 1, 12}, {j, 1, 12}], n+8].{-1, 0, 1/2, 0, 0, 0, 0, 0, 1, 0, 3, 6} // First; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Dec 05 2013, after Maple *)

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

A165799 Number of tilings of a 4 X n rectangle using right trominoes and 2 X 2 tiles.

Original entry on oeis.org

1, 0, 1, 4, 6, 16, 37, 92, 245, 560, 1426, 3720, 9069, 22808, 58177, 145660, 366318, 925536, 2331269, 5872212, 14802941, 37311528, 94038250, 236999064, 597348237, 1505640016, 3794761257, 9564393972, 24106951622, 60759989040, 153141435269, 385986293964

Offset: 0

Alois P. Heinz, Sep 27 2009

			a(4) = 6, because there are 6 tilings of a 4 X 4 rectangle using right trominoes and 2 X 2 tiles:
  .___.___. .___.___. .___.___. .___.___. .___.___. .___.___.
  | . | . | | ._|_. | | ._| . | | ._|_. | | ._|_. | | . |_. |
  |___|___| |_| . |_| |_| |___| |_| ._|_| |_|_. |_| |___| |_|
  | . | . | | |___| | | |___| | | |_| . | | . |_| | | |___| |
  |___|___| |___|___| |___|___| |___|___| |___|___| |___|___|

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,1,9,1,-3,-22,-16,0,-4).

Cf. A165791, A165716, A054854, A054856, A226322.

Column k=4 of A219946.

a:= n-> (Matrix([[4, 1, 0, 1, 0$5]]). Matrix(9, (i,j)-> if i=j-1 then 1 elif j=1 then [1, 1, 9, 1, -3, -22, -16, 0, -4][i] else 0 fi)^n)[1,4]: seq(a(n), n=0..30);

Series[ (-6*x^3 - x + 1) / (4*x^9 + 16*x^7 + 22*x^6 + 3*x^5 - x^4 - 9*x^3 - x^2 - x + 1), {x, 0, 31}] // CoefficientList[#, x] & (* Jean-François Alcover, Jun 18 2013, after Alois P. Heinz *)
LinearRecurrence[{1,1,9,1,-3,-22,-16,0,-4},{1,0,1,4,6,16,37,92,245},40] (* Harvey P. Dale, Nov 09 2024 *)

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

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

A190759 Number of tilings of a 5 X n rectangle using right trominoes and 2 X 2 tiles.

Original entry on oeis.org

1, 0, 4, 0, 16, 0, 136, 0, 1128, 384, 8120, 6912, 60904, 75136, 491960, 720640, 4023592, 6828928, 32819320, 63472640, 270471784, 574543744, 2256221368, 5119155712, 18940876712, 45266369152, 159625747960, 397949457408, 1350573713256

Offset: 0

Alois P. Heinz, May 18 2011

			a(2) = 4, because there are 4 tilings of a 5 X 2 rectangle using right trominoes and 2 X 2 tiles:
.___. .___. .___. .___.
| . | | . | | ._| |_. |
|___| |___| |_| | | |_|
| ._| |_. | |___| |___|
|_| | | |_| | . | | . |
|___| |___| |___| |___|

Alois P. Heinz, Table of n, a(n) for n = 0..650
Index entries for linear recurrences with constant coefficients, signature (0, 13, 2, -57, -12, 190, -10, -453, 396, -2, -88, 308, -160, -80).

Cf. A165799, A165791, A165716, A054854, A054856.

Column k=5 of A219946.

a:= n-> (Matrix(14, (i, j)-> `if`(i=j-1, 1, `if`(i=14, [-80, -160, 308, -88, -2, 396, -453, -10, 190, -12, -57, 2, 13, 0][j], 0)))^n. <<0, 1/4, 0, 1, 0, 4, 0, 16, 0, 136, 0, 1128, 384, 8120>>)[4,1]: seq(a(n), n=0..30);

a[n_] := (MatrixPower[ Table[ If[i == j-1, 1, If[i == 14, {-80, -160, 308, -88, -2, 396, -453, -10, 190, -12, -57, 2, 13, 0}[[j]], 0]], {i, 1, 14}, {j, 1, 14}], n] . {0, 1/4, 0, 1, 0, 4, 0, 16, 0, 136, 0, 1128, 384, 8120})[[4]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 05 2013, translated from Alois P. Heinz's Maple program *)

G.f.: (20*x^12+40*x^11 +18*x^10+52*x^9 +35*x^8-26*x^7 +34*x^6-4*x^5 -21*x^4 +2*x^3 +9*x^2-1) / (-80*x^14-160*x^13 +308*x^12-88*x^11 -2*x^10+396*x^9 -453*x^8-10*x^7 +190*x^6-12*x^5 -57*x^4+2*x^3 +13*x^2-1).

A219862 Number of tilings of a 4 X n rectangle using dominoes and straight (3 X 1) trominoes.

Original entry on oeis.org

1, 1, 7, 41, 184, 1069, 5624, 29907, 161800, 862953, 4631107, 24832532, 133028028, 713283085, 3822965706, 20491221900, 109840081931, 588746006676, 3155783700063, 16915482096570, 90669231898345, 486001022349368, 2605035346917456, 13963368769216664

Offset: 0

Alois P. Heinz, Nov 29 2012

			a(2) = 7, because there are 7 tilings of a 4 X 2 rectangle using dominoes and straight (3 X 1) trominoes:
.___.   .___.   .___.   .___.   .___.   .___.   .___.
| | |   |___|   |___|   | | |   |___|   |___|   | | |
| | |   | | |   |___|   |_|_|   | | |   |___|   |_|_|
|_|_|   | | |   |___|   |___|   |_|_|   | | |   | | |
|___|   |_|_|   |___|   |___|   |___|   |_|_|   |_|_|

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4, 6, 27, -102, 17, -395, 797, -644, 2838, -2657, 2523, -8602, 4310, -8873, 16066, -2769, 18628, -15477, 3863, -27627, 5040, -9300, 19846, 1875, 15731, -6435, 1924, -7786, -680, -4783, 1842, -657, 1108, 32, 734, -278, 88, -32, 10, -58, 13, -3, -1, 0, 1).

Cf. A165716, A165791, A165799, A190759, A202536.

Column k=4 of A219866.

gf:= -(x^42 +x^41 -4*x^40 +4*x^38 -41*x^37 +16*x^36 +45*x^35 +67*x^34 -166*x^33 +282*x^32 -148*x^31 +155*x^30 -405*x^29 +995*x^28 -1118*x^27 +575*x^26 -1863*x^25 +402*x^24 -3552*x^23 +2577*x^22 -406*x^21 +5797*x^20 -741*x^19 +3045*x^18 -5606*x^17 +223*x^16 -4294*x^15 +2924*x^14 -753*x^13 +3011*x^12 -1029*x^11 +811*x^10 -1205*x^9 +248*x^8 -310*x^7 +229*x^6 -17*x^5 +53*x^4 -20*x^3 -3*x^2 -3*x +1) /
(x^45 -x^43 -3*x^42 +13*x^41 -58*x^40 +10*x^39 -32*x^38 +88*x^37 -278*x^36 +734*x^35 +32*x^34 +1108*x^33 -657*x^32 +1842*x^31 -4783*x^30 -680*x^29 -7786*x^28 +1924*x^27 -6435*x^26 +15731*x^25 +1875*x^24 +19846*x^23 -9300*x^22 +5040*x^21 -27627*x^20 +3863*x^19 -15477*x^18 +18628*x^17 -2769*x^16 +16066*x^15 -8873*x^14 +4310*x^13 -8602*x^12 +2523*x^11 -2657*x^10 +2838*x^9 -644*x^8 +797*x^7 -395*x^6 +17*x^5 -102*x^4 +27*x^3 +6*x^2 +4*x -1):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..30);

G.f.: see Maple program.

A202536 Number of tilings of a 4 X n rectangle using straight (3 X 1) trominoes and 2 X 2 tiles.

Original entry on oeis.org

1, 0, 1, 3, 3, 8, 21, 31, 70, 165, 286, 615, 1351, 2548, 5353, 11343, 22320, 46349, 96516, 193944, 400313, 826747, 1678540, 3453642, 7105102, 14498569, 29781633, 61158957, 125108639, 256763850, 526846289, 1079030715, 2213527089, 4540131569, 9304062828

Offset: 0

Alois P. Heinz, Dec 20 2011

			a(3) = 3, because there are 3 tilings of a 4 X 3 rectangle using straight (3 X 1) trominoes and 2 X 2 tiles:
._____.  ._____.  ._._._.
| | | |  |_____|  |_____|
| | | |  | | | |  |_____|
|_|_|_|  | | | |  |_____|
|_____|  |_|_|_|  |_____|
a(4) = 3, because there are 3 tilings of a 4 X 4 rectangle using straight (3 X 1) trominoes and 2 X 2 tiles:
._._____.  ._____._.  ._._._._.
| |_____|  |_____| |  | . | . |
| | . | |  | | . | |  |___|___|
|_|___| |  | |___|_|  | . | . |
|_____|_|  |_|_____|  |___|___|

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1, 1, 11, -9, -8, -48, 29, 23, 115, -44, -31, -173, 35, 19, 174, -18, 2, -119, 10, -14, 56, -8, 12, -19, 4, -5, 5, -1, 1, -1).

Cf. A165716, A165791, A165799, A190759, A219862.

Column k=4 of A219967.

gf:= -(x^3+x-1) *(x^18 -3*x^15 +x^14 +7*x^12 -3*x^11 -11*x^9 +3*x^8 +12*x^6 -x^5 -6*x^3+1) *(x-1)^2 *(x^2+x+1)^2 / (x^30 -x^29 +x^28 -5*x^27 +5*x^26 -4*x^25 +19*x^24 -12*x^23 +8*x^22 -56*x^21 +14*x^20 -10*x^19 +119*x^18 -2*x^17 +18*x^16 -174*x^15 -19*x^14 -35*x^13 +173*x^12 +31*x^11 +44*x^10 -115*x^9 -23*x^8 -29*x^7 +48*x^6 +8*x^5 +9*x^4 -11*x^3 -x^2 -x+1):
a:= n-> coeff(series(gf, x, n+1),x,n);
seq(a(n), n=0..50);

G.f.: see Maple program.

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

Original entry on oeis.org

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

Offset: 0

Gerhard Kirchner, May 09 2022

For tiling algorithm see A351322.

			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 |_|_|

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

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

Maxima
```
See A352589.
```

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

cp's OEIS Frontend

A219987 Number A(n,k) of tilings of a k X n rectangle using dominoes and right trominoes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

A226322 Number of tilings of a 4 X n rectangle using L tetrominoes and 2 X 2 tiles.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A165799 Number of tilings of a 4 X n rectangle using right trominoes and 2 X 2 tiles.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A190759 Number of tilings of a 5 X n rectangle using right trominoes and 2 X 2 tiles.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A219862 Number of tilings of a 4 X n rectangle using dominoes and straight (3 X 1) trominoes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A202536 Number of tilings of a 4 X n rectangle using straight (3 X 1) trominoes and 2 X 2 tiles.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maxima

Formula