A233320 -id:A233320 - cp's OEIS frontend

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

1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 5, 0, 0, 5, 0, 1, 1, 0, 0, 56, 0, 56, 0, 0, 1, 1, 0, 0, 0, 501, 501, 0, 0, 0, 1, 1, 0, 0, 0, 0, 4006, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 27950, 27950, 0, 0, 0, 1, 1, 1, 0, 45, 0, 0, 214689, 0, 214689, 0, 0, 45, 0, 1

Offset: 0

Alois P. Heinz, Dec 09 2013

			A(5,2) = A(2,5) = 5:
  ._________. ._________. ._________. ._________. ._________.
  |_________| | ._____| | | |_____. | |   ._|   | |   |_.   |
  |_________| |_|_______| |_______|_| |___|_____| |_____|___|.
Square array A(n,k) begins:
  1, 1,  1,    1,      1,         1,          1, ...
  1, 0,  0,    0,      0,         1,          0, ...
  1, 0,  0,    0,      0,         5,          0, ...
  1, 0,  0,    0,      0,        56,          0, ...
  1, 0,  0,    0,      0,       501,          0, ...
  1, 1,  5,   56,    501,      4006,      27950, ...
  1, 0,  0,    0,      0,     27950,          0, ...
  1, 0,  0,    0,      0,    214689,          0, ...
  1, 0,  0,    0,      0,   1696781,          0, ...
  1, 0,  0,    0,      0,  13205354,          0, ...
  1, 1, 45, 7670, 890989, 101698212, 7845888732, ...
  ...

Liang Kai, Antidiagonals n = 0..26, flattened (Antidiagonals n = 0..17 from Alois P. Heinz)
R. S. Harris, Counting Polyomino Tilings
Liang Kai, Solving tiling enumeration problems by tensor network contractions, arXiv:2503.17698 [math.CO], 2025.
Wikipedia, Pentomino

Columns (or rows) include: A000012, A054318, A233428, A233429, A174249, A233430.
Cf. A099390, A233320, A230031, A246902, A247117, A278657.
Row sums of A247702, A247703, A247704, A247705, A247706, A247707, A247708, A247709, A247710, A247711, A247712, A247713 give A(n,5).

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

A099390 Array T(m,n) read by antidiagonals: number of domino tilings (or dimer tilings) of the m X n grid (or m X n rectangle), for m>=1, n>=1.

Original entry on oeis.org

0, 1, 1, 0, 2, 0, 1, 3, 3, 1, 0, 5, 0, 5, 0, 1, 8, 11, 11, 8, 1, 0, 13, 0, 36, 0, 13, 0, 1, 21, 41, 95, 95, 41, 21, 1, 0, 34, 0, 281, 0, 281, 0, 34, 0, 1, 55, 153, 781, 1183, 1183, 781, 153, 55, 1, 0, 89, 0, 2245, 0, 6728, 0, 2245, 0, 89, 0, 1, 144, 571, 6336, 14824, 31529, 31529, 14824, 6336, 571, 144, 1

Offset: 1

Ralf Stephan, Oct 16 2004

There are many versions of this array (or triangle) in the OEIS. This is the main entry, which ideally collects together all the references to the literature and to other versions in the OEIS. But see A004003 for further information. - N. J. A. Sloane, Mar 14 2015

			0,  1,  0,   1,    0,    1, ...
1,  2,  3,   5,    8,   13, ...
0,  3,  0,  11,    0,   41, ...
1,  5, 11,  36,   95,  281, ...
0,  8,  0,  95,    0, 1183, ...
1, 13, 41, 281, 1183, 6728, ...

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.
P. E. John, H. Sachs, and H. Zernitz, Problem 5. Domino covers in square chessboards, Zastosowania Matematyki (Applicationes Mathematicae) XIX 3-4 (1987), 635-641.
R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 2nd ed., pp. 547 and 570.
Darko Veljan, Kombinatorika: s teorijom grafova (Croatian) (Combinatorics with Graph Theory) mentions the value 12988816 = 2^4*901^2 for the 8 X 8 case on page 4.

Alois P. Heinz, Table of n, a(n) for n = 1..1035
M. Aanjaneya and S. P. Pal, Faultfree tromino tilings of rectangles, arXiv:math/0610925 [math.CO], 2006.
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
F. Ardila and R. P. Stanley, Tilings, arXiv:math/0501170 [math.CO], 2005.
M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, Journal of Combinatorial Theory, Series A, Volume 77, Issue 1, January 1997, Pages 67-97.
Henry Cohn, 2-adic behavior of numbers of domino tilings, arXiv:math/0008222 [math.CO], 2000.
Henry Cohn, 2-adic behavior of numbers of domino tilings, Electronic Journal of Combinatorics, 6 (1999), #R14.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
Steven R. Finch, The Dimer Problem [From Steven Finch, Apr 20 2019]
Steven R. Finch, Two Dimensional Monomer Dimer Constant [Broken link]
M. E. Fisher, Statistical mechanics of dimers on a plane lattice, Physical Review, 124 (1961), 1664-1672.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 363.
Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter, and Tianyuan Xu, Sandpiles and Dominos, Electronic Journal of Combinatorics, Volume 22(1), 2015.
W. Jockusch, Perfect matchings and perfect squares J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.
Peter E. John and Horst Sachs, On a strange observation in the theory of the dimer problem, arXiv:math/9801094 [math.CO], 1998.
Peter E. John and Horst Sachs, On a strange observation in the theory of the dimer problem, Discrete Math. 216 (2000), no. 1-3, 211-219.
Yuhi Kamio, Junnosuke Koizumi, and Toshihiko Nakazawa, Quadratic residues and domino tilings, arXiv:2311.13597 [math.NT], 2023.
David Klarner and Jordan Pollack, Domino tilings of rectangles with fixed width, Disc. Math. 32 (1980) 45-52, Table 1.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
P. W. Kasteleyn, The statistics of dimers on a lattice, I. the number of dimer arrangements on a quadratic lattice, Physica 27 (1961), 1209-1225.
Douglas M. McKenna, The Art of Space-Filling Domino Curves, Bridges Conference Proceedings, 2024, pp. 319-326.
L. Pachter, Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes, Electronic Journal of Combinatorics 4 (1997), #R29.
J. Propp, Dimers and Dominoes
J. Propp, Enumeration of Matchings: Problems and Progress, arXiv:math/9904150v2 [math.CO], 1999.
Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.
R. C. Read, A Note on Tiling Rectangles with Dominoes, The Fibonacci Quarterly, 18.1 (1980), 24-27.
R. P. Stanley, A combinatorial miscellany
H. N. V. Temperley and Michael E. Fisher, Dimer problem in statistical mechanics -- an exact result, Philos. Mag. (8) 6 (1961), 1061-1063.
Herman Tulleken, Polyominoes 2.2: How they fit together, (2019).
Eric Weisstein's World of Mathematics, Domino Tiling
Eric Weisstein, Illustration for T(4,4) = 36, from Domino Tilings web page (see previous link) [Included with permission]
Index entries for sequences related to dominoes

See A187596 for another version (with m >= 0, n >= 0). See A187616 for a triangular version. See also A187617, A187618.
See also A004003 for more literature on the dimer problem.
Rows 2-13, 16 (without zeros) are A000045, A001835, A005178, A003775, A028468, A028469, A028470, A028471, A028472, A028473, A028474, A241908, A340532.
Main diagonal is A004003.
Cf. A103997, A103999, A233320, A230031, A233427.

(Maple code for the even-numbered rows from N. J. A. Sloane, Mar 15 2015. This is not totally satisfactory since it uses floating point. However, it is useful for getting the initial values quickly.)
Digits:=100;
p:=evalf(Pi);
z:=proc(h,d) global p; evalf(cos( h*p/(2*d+1) )); end;
T:=proc(m,n) global z; round(mul( mul( 4*z(h,m)^2+4*z(k,n)^2, k=1..n), h=1..m)); end;
[seq(T(1,n),n=0..10)]; # A001519
[seq(T(2,n),n=0..10)]; # A188899
[seq(T(3,n),n=0..10)]; # A256044
[seq(T(n,n),n=0..10)]; # A004003

T[?OddQ, ?OddQ] = 0;
T[m_, n_] := Product[2*(2+Cos[2j*Pi/(m+1)]+Cos[2k*Pi/(n+1)]), {k, 1, n/2}, {j, 1, m/2}];
Flatten[Table[Round[T[m-n+1, n]], {m, 1, 12}, {n, 1, m}]] (* Jean-François Alcover, Nov 25 2011, updated May 28 2022 *)

{T(n, k) = sqrtint(abs(polresultant(polchebyshev(n, 2, x/2), polchebyshev(k, 2, I*x/2))))} \\ Seiichi Manyama, Apr 13 2020

T(m, n) = Product_{j=1..ceiling(m/2)} Product_{k=1..ceiling(n/2)} (4*cos(j*Pi/(m+1))^2 + 4*cos(k*Pi/(n+1))^2).

Old link fixed and new link added by Frans J. Faase, Feb 04 2009

Entry edited by N. J. A. Sloane, Mar 15 2015

A230031 Number A(n,k) of tilings of a k X n rectangle using tetrominoes 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, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 4, 0, 4, 0, 1, 1, 0, 0, 23, 23, 0, 0, 1, 1, 0, 9, 0, 117, 0, 9, 0, 1, 1, 1, 0, 0, 454, 454, 0, 0, 1, 1, 1, 0, 25, 0, 2003, 0, 2003, 0, 25, 0, 1, 1, 0, 0, 997, 9157, 0, 0, 9157, 997, 0, 0, 1

Offset: 0

Alois P. Heinz, Nov 29 2013

			A(4,2) = A(2,4) = 4:
  ._______.  ._______.  ._______.  ._______.
  |   |   |  |_______|  | |___. |  | .___| |
  |___|___|  |_______|  |_____|_|  |_|_____|.
Square array A(n,k) begins:
  1, 1,  1,   1,     1,      1,        1,         1,           1, ...
  1, 0,  0,   0,     1,      0,        0,         0,           1, ...
  1, 0,  1,   0,     4,      0,        9,         0,          25, ...
  1, 0,  0,   0,    23,      0,        0,         0,         997, ...
  1, 1,  4,  23,   117,    454,     2003,      9157,       40899, ...
  1, 0,  0,   0,   454,      0,        0,         0,      800290, ...
  1, 0,  9,   0,  2003,      0,   178939,         0,    22483347, ...
  1, 0,  0,   0,  9157,      0,        0,         0,   657253434, ...
  1, 1, 25, 997, 40899, 800290, 22483347, 657253434, 19077209438, ...

Liang Kai, Antidiagonals n = 0..27, flattened (Antidiagonals n = 0..20 from Alois P. Heinz)
S. Butler, J. Ekstrand, S. Osborne, TETRIS Tiling, AMS Spring Central Sectional, Iowa State University, April 27-28 2013
R. S. Harris, Counting Polyomino Tilings
Liang Kai, Solving tiling enumeration problems by tensor network contractions, arXiv:2503.17698 [math.CO], 2025.
Wikipedia, Tetris
Wikipedia, Tetromino

Columns (or rows) include: A000012, A007598, A232757, A174248, A232758, A232684, A232759, A232698, A247113, A232722.
Bisection of main diagonal (even part) gives A263425.
Cf. A099390, A233320, A233427.

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

A364457 Number A(n,k) of tilings of a k X n rectangle using dominoes and 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, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 6, 6, 1, 1, 1, 2, 17, 30, 17, 2, 1, 1, 2, 43, 145, 145, 43, 2, 1, 1, 3, 108, 733, 1352, 733, 108, 3, 1, 1, 4, 280, 3540, 12688, 12688, 3540, 280, 4, 1, 1, 5, 727, 17300, 115958, 226922, 115958, 17300, 727, 5, 1

Offset: 0

Alois P. Heinz, Jul 25 2023

			A(3,2) = A(2,3) = 6:
  .___.   .___.   .___.   .___.   .___.   .___.
  | | |   |___|   | | |   |___|   | ._|   |_. |
  | | |   |___|   |_|_|   | | |   |_| |   | |_|
  |_|_|   |___|   |___|   |_|_|   |___|   |___|  .
.
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,     6,      17,       43,        108,          280, ...
  1, 1,   6,    30,     145,      733,       3540,        17300, ...
  1, 1,  17,   145,    1352,    12688,     115958,      1075397, ...
  1, 2,  43,   733,   12688,   226922,    3927233,     68846551, ...
  1, 2, 108,  3540,  115958,  3927233,  128441094,   4263997124, ...
  1, 3, 280, 17300, 1075397, 68846551, 4263997124, 267855152858, ...

Alois P. Heinz, Table of n, a(n) for n = 0..350
Liang Kai, Solving tiling enumeration problems by tensor network contractions, arXiv:2503.17698 [math.CO], 2025.
Wikipedia, Domino (mathematics)
Wikipedia, Tromino

Columns (or rows) k=0-10 give: A000012, A182097(n) = A000931(n+3), A019439, A364460, A364155, A364556, A364616, A364617, A364632, A364638, A364640.
Main diagonal gives A364504.
Cf. A219866, A219987, A233320.

A(n,k) = A(k,n).

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

A134438 Number of tilings of a 3 X n rectangle with n trominoes.

Original entry on oeis.org

1, 1, 3, 10, 23, 62, 170, 441, 1173, 3127, 8266, 21937, 58234, 154390, 409573, 1086567, 2882021, 7645046, 20279829, 53794224, 142696606, 378522507, 1004078871, 2663452699, 7065162260, 18741269167, 49713692146, 131872134232, 349808216915, 927912454723

Offset: 0

Philippe Deléham, Jan 18 2008

G. Kreweras, Recouvrements d'un rectangle de largeur 3 à l'aide de triminos, Mathématiques et sciences humaines, tome 130 (1995), p. 27-31.

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

Cf. A174248, A174249, A174250, A174251, A174252, A174253, A215826, A233290, A269664, A270063.

Column k=3 of A233320.

a:= n-> (Matrix([[1$2, 0$2, 1, 0]]). Matrix(6, (i,j)-> if i+1=j then 1 elif j=1 then [1, 2, 6, 1, 0, -1][i] else 0 fi)^n)[1,2]: seq(a(n), n=0..30);  # Alois P. Heinz, Oct 09 2008

LinearRecurrence[{1,2,6,1,0,-1},{1,1,3,10,23,62},40] (* Harvey P. Dale, Aug 27 2013 *)

a(n) = a(n-1) +2*a(n-2) +6*a(n-3) +a(n-4) -a(n-6).

G.f.: (1-x^3) / (1-x-2*x^2-6*x^3-x^4+x^6). - Alois P. Heinz, Oct 09 2008

More terms from Alois P. Heinz, Oct 09 2008

A270061 Number A(n,k) of tilings of a k X n rectangle using monominoes and 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, 1, 1, 1, 1, 1, 1, 1, 2, 5, 2, 1, 1, 3, 14, 14, 3, 1, 1, 4, 45, 93, 45, 4, 1, 1, 6, 140, 590, 590, 140, 6, 1, 1, 9, 438, 3710, 7517, 3710, 438, 9, 1, 1, 13, 1371, 23509, 96176, 96176, 23509, 1371, 13, 1, 1, 19, 4287, 148796, 1238818, 2501946, 1238818, 148796, 4287, 19, 1

Offset: 0

Alois P. Heinz, Mar 09 2016

			A(2,3) = A(3,2) = 14:
  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.
  |_____|  |_|_|_|  |_____|  |_| |_|  | |_|_|  | ._|_|  |_. |_|
  |_____|  |_____|  |_|_|_|  |___|_|  |___|_|  |_|_|_|  |_|_|_|
.
  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.
  |_|_|_|  | ._| |  | |_. |  |_|_| |  |_| |_|  |_| ._|  |_|_. |
  |_|_|_|  |_|___|  |___|_|  |_|___|  |_|___|  |_|_|_|  |_|_|_|  .
.
Square array A(n,k) begins:
  1, 1,   1,     1,       1,        1,          1, ...
  1, 1,   1,     2,       3,        4,          6, ...
  1, 1,   5,    14,      45,      140,        438, ...
  1, 2,  14,    93,     590,     3710,      23509, ...
  1, 3,  45,   590,    7517,    96176,    1238818, ...
  1, 4, 140,  3710,   96176,  2501946,   65410388, ...
  1, 6, 438, 23509, 1238818, 65410388, 3473827027, ...

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

Columns (or rows) k=0-10 give: A000012, A000930, A270062, A270063, A270064, A270065, A270066, A270067, A270068, A270069, A270070.
Main diagonal gives A270071.
Cf. A233320.

A360499 Number of ways to tile an n X n square using rectangles with distinct dimensions.

Original entry on oeis.org

1, 1, 21, 269, 4489, 82981, 2995185, 118897973

Offset: 1

Scott R. Shannon, Feb 09 2023

All possible tilings are counted, including those identical by symmetry. Note that distinct dimensions means that, for example, a 1 x 3 rectangle can only be used once, regardless of if it lies horizontally or vertically.

			a(1) = 1 as the only way to tile a 1 x 1 square is with a square with dimensions 1 x 1.
a(2) = 1 as the only way to tile a 2 x 2 square is with a square with dimensions 2 x 2.
a(3) = 21. The possible tilings, excluding those equivalent by symmetry, are:
.
  +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+
  |           |   |   |       |   |       |   |   |           |
  +           +   +---+---+---+   +---+---+   +   +---+---+---+
  |           |   |           |   |       |   |   |           |
  +           +   +           +   +       +   +   +           +
  |           |   |           |   |       |   |   |           |
  +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+
.
The first tiling can occur in 1 way, the second in 8 different ways, the third in 8 different ways and the fourth in 4 different ways, giving 21 ways in total.

Cf. A360498 (oblongs), A182275 (not necessarily distinct dimensions), A004003, A099390, A065072, A233320, A230031.

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A099390 Array T(m,n) read by antidiagonals: number of domino tilings (or dimer tilings) of the m X n grid (or m X n rectangle), for m>=1, n>=1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A134438 Number of tilings of a 3 X n rectangle with n trominoes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

A360499 Number of ways to tile an n X n square using rectangles with distinct dimensions.

Views

Author

Keywords

Comments

Examples

Crossrefs

A215826 Number of ways in which a 9 X n grid can be tiled with trominoes.

Views

Author

Keywords

Links

Crossrefs

A233290 Number of tilings of a 6 X n rectangle with 2n trominoes of any shape.

Views

Author

Keywords

Examples

Links

Crossrefs