A364457 -id:A364457 - cp's OEIS frontend

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

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 4, 4, 1, 1, 1, 2, 7, 14, 7, 2, 1, 1, 2, 15, 41, 41, 15, 2, 1, 1, 3, 30, 143, 184, 143, 30, 3, 1, 1, 4, 60, 472, 1069, 1069, 472, 60, 4, 1, 1, 5, 123, 1562, 5624, 9612, 5624, 1562, 123, 5, 1

Offset: 0

Alois P. Heinz, Nov 30 2012

			A(2,3) = A(3,2) = 4, because there are 4 tilings of a 3 X 2 rectangle using dominoes and straight (3 X 1) trominoes:
  .___.   .___.   .___.   .___.
  | | |   |___|   | | |   |___|
  | | |   |___|   |_|_|   | | |
  |_|_|   |___|   |___|   |_|_|
Square array A(n,k) begins:
  1,  1,  1,    1,     1,      1,        1,         1, ...
  1,  0,  1,    1,     1,      2,        2,         3, ...
  1,  1,  2,    4,     7,     15,       30,        60, ...
  1,  1,  4,   14,    41,    143,      472,      1562, ...
  1,  1,  7,   41,   184,   1069,     5624,     29907, ...
  1,  2, 15,  143,  1069,   9612,    82634,    707903, ...
  1,  2, 30,  472,  5624,  82634,  1143834,  15859323, ...
  1,  3, 60, 1562, 29907, 707903, 15859323, 354859954, ...

Liang Kai, Antidiagonals n = 0..35, flattened (0..22 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.

Columns (or rows) k=0-10 give: A000012, A000931(n+3), A129682, A219867, A219862, A219868, A219869, A219870, A219871, A219872, A219873.
Main diagonal gives: A219874.
Cf. A219987, 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=3, l))+ b(n, subsop(k=2, l))+
         `if`(k `if`(n>=k, b(n, [0$k]), b(k, [0$n])):
seq(seq(A(n, d-n), n=0..d), d=0..10);

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], k = Position[l, 0, 1][[1, 1]]; b[n, ReplacePart[l, k -> 3]] + b[n, ReplacePart[l, k -> 2]] + If[k < Length[l] && l[[k+1]] == 0, b[n, ReplacePart[l, {k -> 1, k+1 -> 1}]], 0] + If[k+1 < Length[l] && l[[k+1]] == 0 && l[[k+2]] == 0, b[n, ReplacePart[l, {k -> 1, k+1 -> 1, 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, 10}] // Flatten (* Jean-François Alcover, Dec 16 2013, translated from Maple *)

A233320 Number A(n,k) of tilings of a k X n rectangle using trominoes of any shape; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 3, 3, 0, 1, 1, 0, 0, 10, 0, 0, 1, 1, 1, 0, 23, 23, 0, 1, 1, 1, 0, 11, 62, 0, 62, 11, 0, 1, 1, 0, 0, 170, 0, 0, 170, 0, 0, 1, 1, 1, 0, 441, 939, 0, 939, 441, 0, 1, 1, 1, 0, 41, 1173, 0, 8342, 8342, 0, 1173, 41, 0, 1

Offset: 0

Alois P. Heinz, Dec 07 2013

Every row and column satisfies a linear recurrence. - Peter Kagey, Jul 17 2019

			Square array A(n,k) begins:
  1, 1,  1,    1,   1,    1,       1, ...
  1, 0,  0,    1,   0,    0,       1, ...
  1, 0,  0,    3,   0,    0,      11, ...
  1, 1,  3,   10,  23,   62,     170, ...
  1, 0,  0,   23,   0,    0,     939, ...
  1, 0,  0,   62,   0,    0,    8342, ...
  1, 1, 11,  170, 939, 8342,   80092, ...
  1, 0,  0,  441,   0,    0,  614581, ...
  1, 0,  0, 1173,   0,    0, 5271923, ...

Liang Kai, Antidiagonals n = 0..35, flattened (Antidiagonals 0..28 from Alois P. Heinz)
Wikipedia, Tromino

Columns (or rows) include: A000012, A001835, A134438, A233339, A233340, A233290, A233343, A269958, A215826, A269959, A269664.

Cf. A099390, A230031, A233427, A270061, A364457.

A(n,k) = 0 <=> n*k mod 3 > 0.

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.

Original entry on oeis.org

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

A364504 Number of tilings of an n X n square using dominoes and trominoes (of any shape).

Original entry on oeis.org

1, 0, 2, 30, 1352, 226922, 128441094, 267855152858, 1990875917805852, 52918918728713551244, 5046393600526600826576990, 1722423352379200292770200349728, 2106175531602971710801901685263906946, 9224774497259881798661234516031754156588512, 144713995908210595144464778124853904625705818728754

Offset: 0

Alois P. Heinz, Jul 26 2023

nonn

David Radcliffe, Table of n, a(n) for n = 0..17 (computed by Liang Kai).
Liang Kai, Solving tiling enumeration problems by tensor network contractions, arXiv:2503.17698 [math.CO], 2025.
Liang Kai, Tiling, GitHub repository.
Wikipedia, Domino (mathematics)
Wikipedia, Tromino

Main diagonal of A364457.

Cf. A219874, A219994.

a(n) = A364457(n,n).

Terms n>=4 had to be corrected as was pointed out by Martin Fuller and David Radcliffe - Alois P. Heinz, Apr 05 2025

a(13)-a(17) from David Radcliffe, Apr 07 2025

A019439 Number of ways of tiling a 2 X n rectangle with dominoes and trominoes.

Original entry on oeis.org

1, 1, 2, 6, 17, 43, 108, 280, 727, 1875, 4832, 12470, 32191, 83075, 214372, 553214, 1427673, 3684333, 9507936, 24536616, 63320419, 163407771, 421697922, 1088253936, 2808400703, 7247494517, 18703234038, 48266468208, 124558777387, 321442392689, 829529751892, 2140724511882

Offset: 0

N. J. A. Sloane, Oct 04 2008

The old entry with this sequence number was a duplicate of A007737.

Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.

Alois P. Heinz, Table of n, a(n) for n = 0..2430
Index entries for linear recurrences with constant coefficients, signature (2,0,3,2,1,-1).

Column k=2 of A364457.

a:= n-> (Matrix([[1, 1, 0, 0, 1, 1]]). Matrix (6, (i,j)-> if i=j-1 then 1 elif j=1 then [2, 0, 3, 2, 1, -1][i] else 0 fi)^n)[1,2]: seq(a(n), n=0..30); # Alois P. Heinz, Sep 24 2009

LinearRecurrence[{2, 0, 3, 2, 1, -1}, {1, 1, 2, 6, 17, 43}, 40] // Rest (* Jean-François Alcover, Feb 18 2016 *)

G.f.: -(x^3+x-1)/(x^6-x^5-2*x^4-3*x^3-2*x+1). - Alois P. Heinz, Sep 24 2009

More terms from Alois P. Heinz, Sep 24 2009

a(0)=1 prepended by Alois P. Heinz, Jul 25 2023

A364155 Number of tilings of a 4 X n rectangle using dominoes and trominoes (of any shape).

Original entry on oeis.org

1, 1, 17, 145, 1352, 12688, 115958, 1075397, 9935791, 91795006, 848550447, 7841290657, 72469286374, 669744449380, 6189592846538, 57202915584686, 528655401099501, 4885709752947038, 45152583446359974, 417289539653241534, 3856491950197255757, 35640791884109598908

Offset: 0

Alois P. Heinz, Jul 28 2023

			a(2) = 17:
  .___.  .___.  .___.  .___.  .___.  .___.  .___.  .___.  .___.
  | | |  |___|  |___|  | | |  |___|  |___|  | | |  | ._|  |_. |
  | | |  | | |  |___|  |_|_|  | | |  |___|  |_|_|  |_| |  | |_|
  |_|_|  | | |  |___|  |___|  |_|_|  | | |  | | |  |___|  |___|
  |___|  |_|_|  |___|  |___|  |___|  |_|_|  |_|_|  |___|  |___|
.
  .___.  .___.  .___.  .___.  .___.  .___.  .___.  .___.
  |___|  |___|  | | |  | | |  |_. |  | ._|  |_. |  | ._|
  | ._|  |_. |  | |_|  |_| |  | |_|  |_| |  | |_|  |_| |
  |_| |  | |_|  |_| |  | |_|  | | |  | | |  |_| |  | |_|
  |___|  |___|  |___|  |___|  |_|_|  |_|_|  |___|  |___|  .

Alois P. Heinz, Table of n, a(n) for n = 0..1036
Wikipedia, Domino (mathematics)
Wikipedia, Tromino
Index entries for linear recurrences with constant coefficients, signature (4,35,109,99,452,-335, -2794,3364,-3922,-12030,5208,-9998,-27774,69116,257069,-243226,413937,-701476, 189181,-1162643,1664063,-1044441,1530359,-1050005,883613,-1670818,1231995, -410529,309573,-459720,336502,-139986,56406,-10114,12166,-17169,3519,653,112, -211,187,-10,-15,-4,1).

Column k=4 of A364457.

G.f.: -(x^42 -3*x^41 +2*x^40 -27*x^39 +20*x^38 -47*x^37 +679*x^36 -807*x^35 +971*x^34 -3668*x^33 +4911*x^32 -17380*x^31 +41345*x^30 -21439*x^29 +1694*x^28 -117750*x^27 +184140*x^26 -41964*x^25 +99138*x^24 -180813*x^23 +70242*x^22 -240711*x^21 +162785*x^20 +46241*x^19 +117557*x^18 -67141*x^17 +25483*x^16 -51680*x^15 -25799*x^14 +7385*x^13 +5758*x^12 -1195*x^11 +1461*x^10 +2940*x^9 -1582*x^8 +1207*x^7 +281*x^6 -199*x^5 -31*x^4 -67*x^3 -22*x^2 -3*x +1) / (x^45 -4*x^44 -15*x^43 -10*x^42 +187*x^41 -211*x^40 +112*x^39 +653*x^38 +3519*x^37 -17169*x^36 +12166*x^35 -10114*x^34 +56406*x^33 -139986*x^32 +336502*x^31 -459720*x^30 +309573*x^29 -410529*x^28 +1231995*x^27 -1670818*x^26 +883613*x^25 -1050005*x^24 +1530359*x^23 -1044441*x^22 +1664063*x^21 -1162643*x^20 +189181*x^19 -701476*x^18 +413937*x^17 -243226*x^16 +257069*x^15 +69116*x^14 -27774*x^13 -9998*x^12 +5208*x^11 -12030*x^10 -3922*x^9 +3364*x^8 -2794*x^7 -335*x^6 +452*x^5 +99*x^4 +109*x^3 +35*x^2 +4*x -1).

Terms n>=4 had to be corrected as was pointed out by Martin Fuller and David Radcliffe - Alois P. Heinz, Apr 05 2025

A364460 Number of tilings of a 3 X n rectangle using dominoes and trominoes (of any shape).

Original entry on oeis.org

1, 1, 6, 30, 145, 733, 3540, 17300, 84479, 411963, 2011408, 9816506, 47911847, 233851991, 1141365064, 5570761346, 27189615925, 132706261547, 647709321582, 3161321546320, 15429691961077, 75308819284819, 367565220881250, 1794002281279416, 8756117243124305, 42736617464745197

Offset: 0

Alois P. Heinz, Jul 25 2023

			a(2) = 6:
  .___.   .___.   .___.   .___.   .___.   .___.
  | | |   |___|   | | |   |___|   | ._|   |_. |
  | | |   |___|   |_|_|   | | |   |_| |   | |_|
  |_|_|   |___|   |___|   |_|_|   |___|   |___|  .

Alois P. Heinz, Table of n, a(n) for n = 0..1453
Wikipedia, Domino (mathematics)
Wikipedia, Tromino
Index entries for linear recurrences with constant coefficients, signature (3,6,13,0,53,18,69,48,35,-125,-76,-24,38,8,18,1,-3,-1).

Column k=3 of A364457.

Cf. A133872.

G.f.: -(x^15 +2*x^14 +4*x^13 -5*x^12 -9*x^11 -18*x^10 +16*x^9 +5*x^8 +8*x^7 -10*x^6 +13*x^5 -6*x^4 +7*x^3 +3*x^2 +2*x -1) / (x^18 +3*x^17 -x^16 -18*x^15 -8*x^14 -38*x^13 +24*x^12 +76*x^11 +125*x^10 -35*x^9 -48*x^8 -69*x^7 -18*x^6 -53*x^5 -13*x^3 -6*x^2 -3*x +1).

a(n) mod 2 = A133872(n).

A364556 Number of tilings of a 5 X n rectangle using dominoes and trominoes (of any shape).

Original entry on oeis.org

1, 2, 43, 733, 12688, 226922, 3927233, 68846551, 1204757533, 21062468900, 368521437132, 6445706387345, 112749099291387, 1972235696214897, 34498222540798726, 603446574091501719, 10555520988321750183, 184637793249606497610, 3229696298942838688793, 56494043669663414794810

Offset: 0

Alois P. Heinz, Jul 28 2023

nonn

			a(1) = 2:
    ._.   ._.
    | |   | |
    | |   |_|
    |_|   | |
    | |   | |
    |_|   |_|   .

Alois P. Heinz, Table of n, a(n) for n = 0..805
Wikipedia, Domino (mathematics)
Wikipedia, Tromino

Column k=5 of A364457.

Terms n>=4 had to be corrected as was pointed out by Martin Fuller and David Radcliffe - Alois P. Heinz, Apr 05 2025

A364616 Number of tilings of a 6 X n rectangle using dominoes and trominoes (of any shape).

Original entry on oeis.org

1, 2, 108, 3540, 115958, 3927233, 128441094, 4263997124, 141186107223, 4671227129777, 154679198549385, 5119908497703914, 169488865440883593, 5610718094136694973, 185732776135043052107, 6148417237267189975927, 203533740825252409802705, 6737670699036802296758849

Offset: 0

Alois P. Heinz, Jul 29 2023

nonn

			a(1) = 2:
    ._.   ._.
    | |   | |
    |_|   | |
    | |   |_|
    |_|   | |
    | |   | |
    |_|   |_|   .

Alois P. Heinz, Table of n, a(n) for n = 0..500
Wikipedia, Domino (mathematics)
Wikipedia, Tromino

Column k=6 of A364457.

Terms n>=4 had to be corrected as was pointed out by Martin Fuller and David Radcliffe - Alois P. Heinz, Apr 05 2025

A364617 Number of tilings of a 7 X n rectangle using dominoes and trominoes (of any shape).

Original entry on oeis.org

1, 3, 280, 17300, 1075397, 68846551, 4263997124, 267855152858, 16785795917908, 1051116421516975, 65871551452359237, 4126577980480405170, 258538236543240798654, 16197912784372244064693, 1014813990592495583029006, 63579642939479330198729573, 3983348112669764700919476270

Offset: 0

Alois P. Heinz, Jul 29 2023

nonn

			a(1) = 3:
    ._.   ._.   ._.
    | |   | |   | |
    |_|   |_|   | |
    | |   | |   |_|
    |_|   | |   | |
    | |   |_|   |_|
    | |   | |   | |
    |_|   |_|   |_|   .

Alois P. Heinz, Table of n, a(n) for n = 0..557
Wikipedia, Domino (mathematics)
Wikipedia, Tromino

Column k=7 of A364457.

Terms n>=4 had to be corrected as was pointed out by Martin Fuller and David Radcliffe - Alois P. Heinz, Apr 05 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A233320 Number A(n,k) of tilings of a k X n rectangle using trominoes of any shape; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

A364504 Number of tilings of an n X n square using dominoes and trominoes (of any shape).

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A019439 Number of ways of tiling a 2 X n rectangle with dominoes and trominoes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A364155 Number of tilings of a 4 X n rectangle using dominoes and trominoes (of any shape).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A364460 Number of tilings of a 3 X n rectangle using dominoes and trominoes (of any shape).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A364556 Number of tilings of a 5 X n rectangle using dominoes and trominoes (of any shape).

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A364616 Number of tilings of a 6 X n rectangle using dominoes and trominoes (of any shape).

Views

Author