A226322 -id:A226322 - cp's OEIS frontend

A174248 Number of tilings of a 4 X n rectangle with n tetrominoes of any shape.

1, 1, 4, 23, 117, 454, 2003, 9157, 40899, 179399, 796558, 3546996, 15747348, 69834517, 310058192, 1376868145, 6112247118, 27132236455, 120453362938, 534754586459, 2373975139658, 10538953415410, 46786795734201, 207705902269424, 922089495910044, 4093525019450760

Offset: 0

Bob Harris (me13013(AT)gmail.com), Mar 13 2010

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.
S. Butler, J. Ekstrand, and S. Osborne, TETRIS Tiling, AMS Spring Central Sectional, Iowa State University, April 27-28 2013.
R. S. Harris, Counting Nonomino Tilings and Other Things of that Ilk, G4G9 Gift Exchange book, 2010.
R. S. Harris, Counting Polyomino Tilings.
Wikipedia, Tetris.
Wikipedia, Tetromino.
Index entries for linear recurrences with constant coefficients, signature (2, 8, 8, 54, -77, -290, -76, -548, 469, 2258, 414, 1970, -1053, -6885, -1620, -3349, 1102, 9566, 3210, 2786, -489, -6047, -2600, -1102, 60, 1476, 659, 225, 39, -123, -50, -13, -3, 3, 1).

Cf. A134438, A174249, A226322, A232497, A232684, A232698, A232722, A233191, A233266.

Column k=4 of A230031.

G.f.: -(x^31 +3*x^30 -2*x^29 -7*x^28 -25*x^27 -78*x^26 +23*x^25 +116*x^24 +217*x^23 +604*x^22 -21*x^21 -556*x^20 -649*x^19 -1621*x^18 -175*x^17 +727*x^16 +523*x^15 +1707*x^14 +236*x^13 -470*x^12 -143*x^11 -749*x^10 -133*x^9 +166*x^8 +15*x^7 +126*x^6 +27*x^5 -23*x^4 -x^3 -6*x^2 -x +1) / (x^35 +3*x^34 -3*x^33 -13*x^32 -50*x^31 -123*x^30 +39*x^29 +225*x^28 +659*x^27 +1476*x^26 +60*x^25 -1102*x^24 -2600*x^23 -6047*x^22 -489*x^21 +2786*x^20 +3210*x^19 +9566*x^18 +1102*x^17 -3349*x^16 -1620*x^15 -6885*x^14 -1053*x^13 +1970*x^12 +414*x^11 +2258*x^10 +469*x^9 -548*x^8 -76*x^7 -290*x^6 -77*x^5 +54*x^4 +8*x^3 +8*x^2 +2*x -1). - Alois P. Heinz, Nov 26 2013

a(0) inserted, a(11)-a(22) from Alois P. Heinz, May 07 2013

a(23)-a(25) from Alois P. Heinz, Nov 26 2013

A084480 Number of tilings of a 4 X 2n rectangle with L tetrominoes.

Original entry on oeis.org

1, 2, 10, 42, 182, 790, 3432, 14914, 64814, 281680, 1224182, 5320310, 23122148, 100489226, 436727814, 1898026232, 8248853134, 35849651070, 155803171860, 677123141810, 2942788286798, 12789406189672, 55582969192486, 241564496305670, 1049843265359828

Offset: 0

Ralf Stephan, May 27 2003

Colin Barker, 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. 2.
Cristopher Moore, Some Polyomino Tilings of the Plane, arXiv:9905012 [math.CO], 1999.
Index entries for linear recurrences with constant coefficients, signature (4,2,-1,-4,-4,-2).

Cf. A084478, A084479, A084477, A084481, A174248, A226322, A232497.

LinearRecurrence[{4, 2, -1, -4, -4, -2}, {1, 2, 10, 42, 182, 790}, 25] (* Jean-François Alcover, Feb 25 2020 *)

Vec((1 - 2*x - x^3) / (1 - 4*x - 2*x^2 + x^3 + 4*x^4 + 4*x^5 + 2*x^6) + O(x^30)) \\ Colin Barker, Mar 28 2017

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

a(n) = 4*a(n-1) + 2*a(n-2) - a(n-3) - 4*a(n-4) - 4*a(n-5) - 2*a(n-6) for n>5. - Colin Barker, Mar 28 2017

Inserted a(0)=1 by Alois P. Heinz, May 01 2013

A165791 Number of tilings of a 4 X n rectangle using dominoes and right trominoes.

Original entry on oeis.org

1, 1, 11, 55, 380, 2319, 15171, 96139, 619773, 3962734, 25445515, 163048957, 1045897075, 6705473761, 43001795070, 275730928993, 1768128097215, 11337760387473, 72702310606249, 466192677008538, 2989403530821497, 19169143325987983, 122919655766448729

Offset: 0

Alois P. Heinz, Sep 26 2009

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

Alois P. Heinz, Table of n, a(n) for n = 0..400
Index entries for linear recurrences with constant coefficients, signature (4, 21, -25, -65, -17, 24, -11, -15, 9).

Cf. A165716, A127870, A054854, A226322.

Column k=4 of A219987.

a:= n-> (Matrix([[619773, 96139, 15171, 2319, 380, 55, 11, 1, 1]]). Matrix(9, (i,j)-> if i=j-1 then 1 elif j=1 then [4, 21, -25, -65, -17, 24, -11, -15, 9][i] else 0 fi)^n)[1,9]: seq(a(n), n=0..25);

a[n_] := {619773, 96139, 15171, 2319, 380, 55, 11, 1, 1} . MatrixPower[ Table[ Which[i == j-1, 1, j == 1, {4, 21, -25, -65, -17, 24, -11, -15, 9}[[i]], True, 0], {i, 1, 9}, {j, 1, 9}], n] // Last; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Dec 04 2013, translated and adapted from Alois P. Heinz's Maple program *)

G.f.: (2*x^8-5*x^7+2*x^6-x^5-19*x^4-15*x^3+14*x^2+3*x-1) / (9*x^9-15*x^8-11*x^7+24*x^6-17*x^5-65*x^4-25*x^3+21*x^2+4*x-1).

A232497 Number of tilings of a 4 X n rectangle using L and Z tetrominoes.

Original entry on oeis.org

1, 0, 2, 6, 14, 32, 102, 238, 652, 1696, 4480, 11658, 30870, 80644, 212292, 556858, 1463390, 3840686, 10090218, 26490280, 69575414, 182693434, 479789138, 1259906496, 3308668718, 8688615148, 22817011182, 59918425698, 157349755400, 413208421354, 1085110433096

Offset: 0

Alois P. Heinz, Nov 24 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.
Wikipedia, Tetromino
Index entries for linear recurrences with constant coefficients, signature (0,5,7,2,-13,-13,-6,-6,0,-4,0,-2).

Cf. A084480, A174248, A226322, A233139, A233191, A233266.

a:= n-> coeff(series(-(x^6-x^5-2*x^4+x^3+3*x^2-1)/
    (2*x^12+4*x^10+6*x^8+6*x^7+13*x^6+13*x^5-2*x^4-7*x^3-5*x^2+1),
    x, n+1), x, n);
seq(a(n), n=0..40);

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

A233191 Number of tilings of a 4 X n rectangle using L and T tetrominoes.

Original entry on oeis.org

1, 0, 2, 4, 12, 16, 76, 128, 386, 832, 2368, 5024, 13946, 31680, 82632, 193696, 498174, 1182464, 2993384, 7213648, 18061074, 43832960, 109163384, 266217472, 660116398, 1615451648, 3995295112, 9796774896, 24189684402, 59396496000, 146494223160, 360026507808

Offset: 0

Alois P. Heinz, Dec 05 2013

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

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.
Wikipedia, Tetromino
Index entries for linear recurrences with constant coefficients, signature (0, 4, 4, 5, -8, 4, 12, -18, -8, 0, 0, -8).

Cf. A084480, A174248, A226322, A230031, A232497, A233139, A233266.

gf:= (2*x^6+x^4+2*x^2-1) / (-8*x^12 -8*x^9 -18*x^8
     +12*x^7 +4*x^6 -8*x^5 +5*x^4 +4*x^3 +4*x^2 -1):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..40);

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

A233266 Number of tilings of a 4 X n rectangle using tetrominoes of shapes L, T, Z.

Original entry on oeis.org

1, 0, 2, 10, 24, 70, 276, 820, 2616, 8702, 27902, 89500, 291050, 939222, 3029950, 9798606, 31657182, 102237766, 330356240, 1067310022, 3447911968, 11139391996, 35988377472, 116265759012, 375619824338, 1213515477460, 3920484872552, 12665878390278

Offset: 0

Alois P. Heinz, Dec 06 2013

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

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.
Wikipedia, Tetromino
Index entries for linear recurrences with constant coefficients, signature (2, 4, 4, -6, -28, 15, 4, -13, 20, -4, 16, -10, 8, -2).

Cf. A084480, A174248, A226322, A230031, A232497, A233139, A233191, A242636.

G.f.: (x^8 -4*x^7 +3*x^6 -2*x^5 -2*x^4 -2*x^3 +2*x^2 +2*x -1) / (-2*x^14 +8*x^13 -10*x^12 +16*x^11 -4*x^10 +20*x^9 -13*x^8 +4*x^7 +15*x^6 -28*x^5 -6*x^4 +4*x^3 +4*x^2 +2*x -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).

A233139 Number of tilings of a 4 X n rectangle using T and Z tetrominoes.

Original entry on oeis.org

1, 0, 0, 0, 2, 4, 8, 18, 44, 104, 242, 564, 1320, 3090, 7228, 16904, 39538, 92484, 216328, 506002, 1183564, 2768424, 6475506, 15146580, 35428712, 82869778, 193837148, 453396168, 1060519538, 2480615780, 5802302024, 13571915922, 31745486700, 74254506984

Offset: 0

Alois P. Heinz, Dec 04 2013

			a(5) = 4:
._____.___.  .___._____.  ._._____._.  ._._____._.
|_. ._| ._|  |_. |_. ._|  | |_. ._| |  | |_. ._| |
| |_|___| |  | |___|_| |  | ._|_|_. |  | ._|_|_. |
| ._| |_. |  | ._| |_. |  |_| |_. |_|  |_| ._| |_|
|_|_____|_|  |_|_____|_|  |_____|___|  |___|_____|.

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

Cf. A084480, A174248, A226322, A230031, A232497, A233191, A233266.

a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <2|1|0|2>>^n.
        <<1, 0, 0, 0>>)[1, 1]:
seq(a(n), n=0..40);

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

a(n) = 2*a(n-1)+a(n-3)+2*a(n-4) for n>3, a(0)=1, a(1)=a(2)=a(3)=0.

A242636 Number of tilings of a 4 X n rectangle using tetrominoes of shapes L, Z, O.

Original entry on oeis.org

1, 0, 3, 12, 23, 94, 289, 842, 2771, 8510, 26411, 83122, 258199, 805914, 2517287, 7846960, 24490017, 76416244, 238387767, 743840496, 2320800841, 7240890040, 22592311143, 70488834118, 219928631821, 686190651342, 2140948175385, 6679872756528, 20841562274863

Offset: 0

Alois P. Heinz, May 19 2014

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

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.
Wikipedia, Tetromino
Index entries for linear recurrences with constant coefficients, signature (0,6,13,3,-18,-13,-3,1,-2,-4,0,-2).

Cf. A084480, A174248, A226322, A230031, A232497, A233139, A233191, A233266.

gf:= (x^6-x^5-2*x^4+x^3+3*x^2-1) / (-2*x^12 -4*x^10 -2*x^9 +x^8 -3*x^7 -13*x^6 -18*x^5 +3*x^4 +13*x^3 +6*x^2 -1):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..40);

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

cp's OEIS Frontend

A174248 Number of tilings of a 4 X n rectangle with n tetrominoes of any shape.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A084480 Number of tilings of a 4 X 2n rectangle with L tetrominoes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A165791 Number of tilings of a 4 X n rectangle using dominoes and right trominoes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A232497 Number of tilings of a 4 X n rectangle using L and Z tetrominoes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A233191 Number of tilings of a 4 X n rectangle using L and T tetrominoes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A233266 Number of tilings of a 4 X n rectangle using tetrominoes of shapes L, T, Z.

Views

Author

Keywords

Examples

Links

Crossrefs

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

A233139 Number of tilings of a 4 X n rectangle using T and Z tetrominoes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula