A099390 -id:A099390 - cp's OEIS frontend

A348452 Irregular triangle read by rows: T(n,k) (n >= 1, 1 <= k <= n^2) is the number of ways to tile an n X n chessboard with k rook-connected polyominoes of equal area.

1, 1, 2, 0, 1, 1, 0, 10, 0, 0, 0, 0, 0, 1, 1, 70, 0, 117, 0, 0, 0, 36, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 4006, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 80518, 264500, 442791, 0, 451206, 0, 0, 178939, 0, 0, 80092, 0, 0, 0, 0, 0, 6728, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 158753814, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 1

N. J. A. Sloane, Oct 27 2021

The board has n^2 squares. The colors do not matter. T(n,k) is zero unless k divides n^2. The tiles are rook-connected polygons made from n^2/k squares.
This is the "labeled" version of the problem. Symmetries of the square are not taken into account. Rotations and reflections count as different.
A348453 (the main entry for this problem) displays the same data in a more compact way (by omitting the zero entries from each row).
The data is taken from A004003, A172477, and Schutzman & MGGG (2018).

			The first seven rows of the triangle are:
1,
1, 2, 0, 1,
1, 0, 10, 0, 0, 0, 0, 0, 1,
1, 70, 0, 117, 0, 0, 0, 36, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 4006, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 80518, 264500, 442791, 0, 451206, 0, 0, 178939, 0, 0, 80092, 0, 0, 0, 0, 0, 6728, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 158753814, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
...
The domino is the only polyomino of area 2, and the 36 ways to tile a 4 X 4 square with dominoes are shown in one of the links.

Moon Duchin, Graphs, Geometry and Gerrymandering”, Talk at Celebration of Mind Conference, Oct 23 2021.
P. W. Kasteleyn, The Statistics of Dimers on a Lattice, Physica, 27 (1961), 1209-1225.
P. W. Kasteleyn, Dimer statistics and phase transitions, J. Mathematical Phys. 4 1963 287-293. MR0153427 (27 #3394).
Zach Schutzman and MGGG, The Known Sizes of Grid Metagraphs, Metric Geometry and Gerrymandering Group (MGGG), Boston, Oct 01 2018.
N. J. A. Sloane, Illustration for T(3,3) = 10
N. J. A. Sloane, Illustration for T(4,2) = 70 [Labels give code, B = length of internal boundary, C = number of internal corners, G = group order, # = number of this type. Note that (B,C) determines the type]
N. J. A. Sloane, Illustration for T(4,8) = 36 [Slide from an old talk of mine]
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences: An illustrated guide with many unsolved problems, Guest Lecture given in Doron Zeilberger's Experimental Mathematics Math640 Class, Rutgers University, Spring Semester, Apr 28 2022: Slides; Slides (an alternative source).

Cf. A348453. A348454 and A348455 are similar triangles with the data in each row reversed. The row sums are in A348789.

See also A004003, A099390, A172477, A348456.

A formula for T(n, n^2/2) was found by Kastelyn (see A004003 and A099390). T(n,n) is studied in A172477.

More than the usual number of terms are given, in order to show the first seven rows.

A348453 Irregular triangle read by rows: T(n,k) (n >= 1, 1 <= k <= number of divisors of n^2) is the number of ways to tile an n X n chessboard with d_k rook-connected polyominoes of equal area, where d_k is the k-th divisor of n^2.

Original entry on oeis.org

1, 1, 2, 1, 1, 10, 1, 1, 70, 117, 36, 1, 1, 4006, 1, 1, 80518, 264500, 442791, 451206, 178939, 80092, 6728, 1, 1, 158753814, 1, 7157114189

Offset: 1

N. J. A. Sloane, Oct 27 2021

The board has n^2 squares. The colors do not matter. The tiles are rook-connected polygons made from n^2/d_k squares.
This is the "labeled" version of the problem. Symmetries of the square are not taken into account. Rotations and reflections count as different.
A348452 displays the same data in a less compact way. The present triangle is obtained by omitting the zero entries from A348452.
The data is taken from A004003, A172477, A348456, and Schutzman & MGGG (2018).
T(8,2) = 7157114189 (see A348456). T(8,3) is presently unknown.

			The first eight rows of the triangle are:
  1,
  1, 2, 1,
  1, 10, 1,
  1, 70, 117, 36, 1,
  1, 4006, 1,
  1, 80518, 264500, 442791, 451206, 178939, 80092, 6728, 1,
  1, 158753814, 1,
  1, 7157114189, ?, 187497290034, ?, ?, 1,
  ...
The corresponding divisors d_k are:
  1,
  1, 2, 4,
  1, 3, 9,
  1, 2, 4, 8, 16,
  1, 5, 25,
  ...
The domino is the only polyomino of area 2, and the 36 ways to tile a 4 X 4 square with dominoes are shown in one of the links.

Moon Duchin, Graphs, Geometry and Gerrymandering”, Talk at Celebration of Mind Conference, Oct 23 2021.
P. W. Kasteleyn, The Statistics of Dimers on a Lattice, Physica, 27 (1961), 1209-1225.
P. W. Kasteleyn, Dimer statistics and phase transitions, J. Mathematical Phys. 4 1963 287-293. MR0153427 (27 #3394).
Zach Schutzman and MGGG, The Known Sizes of Grid Metagraphs, Metric Geometry and Gerrymandering Group (MGGG), Boston, Oct 01 2018.
N. J. A. Sloane, Illustration for T(3,2) = 10
N. J. A. Sloane, Illustration for T(4,2) = 70 [Labels give code, B = length of internal boundary, C = number of internal corners, G = group order, # = number of this type. Note that (B,C) determines the type]
N. J. A. Sloane, Illustration for T(4,4) = 36 [Slide from an old talk of mine]
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 21.

Cf. A348452. A348454 and A348455 are similar triangles with the data in each row reversed.
See also A004003, A099390, A172477, A348456.
Cf. A048691 (row lengths).

A formula for T(n, n^2/2) was found by Kastelyn (see A004003 and A099390). T(n,n) is studied in A172477.

T(8,2) added May 04 2022 (see A348456) - N. J. A. Sloane, May 05 2022

A360256 Number of ways to tile an n X n square using rectangles with distinct height X width dimensions.

Original entry on oeis.org

1, 1, 33, 513, 14409, 693025, 50447161

Offset: 1

Scott R. Shannon, Feb 17 2023

All possible tilings are counted, including those identical by symmetry. Note that distinct height X width dimensions means that, for example, a 1 X 3 rectangle can be used twice, once in a horizontal (1 X 3) and once in a vertical (3 X 1) direction.

			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) = 33. The possible tilings, excluding those equivalent by symmetry, are:
.
  +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+
  |   |       |   |   |       |   |       |   |   |           |   |   |       |
  +---+---+---+   +---+---+---+   +---+---+   +   +---+---+---+   +---+---+---+
  |   |       |   |           |   |       |   |   |           |   |       |   |
  +   +       +   +           +   +       +   +   +           +   +       +   +
  |   |       |   |           |   |       |   |   |           |   |       |   |
  +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+
.
The first tiling can occur in 4 different ways, the second in 8 different ways, the third in 8 different ways, the fourth in 4 different ways and the fifth in 8 different ways. There is also the single 3 X 3 rectangle. This gives 33 ways in total.

Cf. A360725 (oblongs), A360499, A360498, A182275, A004003, A099390, A065072.

A360498 Number of ways to tile an n X n square using oblongs with distinct dimensions.

Original entry on oeis.org

0, 0, 4, 12, 256, 3620, 87216, 2444084, 87181220

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 oblong can only be used once, regardless of if it lies horizontally or vertically.

			a(1) = 0 as no distinct oblongs can tile a square with dimensions 1 x 1.
a(2) = 0 as no distinct oblongs can tile a square with dimensions 2 x 2.
a(3) = 4. There is one tiling, excluding those equivalent by symmetry:
.
  +---+---+---+
  |           |
  +---+---+---+
  |           |
  +           +
  |           |
  +---+---+---+
.
This tiling can occur in 4 different ways, giving 4 ways in total.
a(4) = 12. The possible tilings, excluding those equivalent by symmetry, are:
.
  +---+---+---+---+   +---+---+---+---+
  |   |           |   |               |
  +   +           +   +---+---+---+---+
  |   |           |   |               |
  +---+---+---+---+   +               +
  |               |   |               |
  +               +   +               +
  |               |   |               |
  +---+---+---+---+   +---+---+---+---+
.
The first tiling can occur in 8 different way and the second in 4 different ways, giving 12 ways in total.

Cf. A360499 (rectangles), A004003, A099390, A065072, A233320, A230031.

A028473 Number of perfect matchings in graph P_{11} X P_{2n}.

Original entry on oeis.org

1, 144, 51205, 21001799, 8940739824, 3852472573499, 1666961188795475, 722364079570222320, 313196612952258199679, 135818983640055277506397, 58902468764522025160456848, 25545661075321867247577262777, 11079103257893769392837296086025

Offset: 0

Per H. Lundow

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200
Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research report, No 12, 1996, Department of Math., Umea University, Sweden.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
Vladeta Jovovic, Explicit formula, generating function and recurrence
Index entries for linear recurrences with constant coefficients, signature (780, -194881, 22377420, -1419219792, 55284715980, -1410775106597, 24574215822780, -300429297446885, 2629946465331120, -16741727755133760, 78475174345180080, -273689714665707178, 716370537293731320, -1417056251105102122, 2129255507292156360, -2437932520099475424, 2129255507292156360, -1417056251105102122, 716370537293731320, -273689714665707178, 78475174345180080, -16741727755133760, 2629946465331120, -300429297446885, 24574215822780, -1410775106597, 55284715980, -1419219792, 22377420, -194881, 780, -1).

Row 11 of array A099390.

Bisection of A210724 (even part).

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

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

Title corrected by Sergey Perepechko, Nov 27 2012

A028474 Number of perfect matchings in graph P_{12} X P_{n}.

Original entry on oeis.org

1, 1, 233, 2131, 145601, 2332097, 106912793, 2188978117, 82741005829, 1937528668711, 65743732590821, 1666961188795475, 53060477521960000, 1412218550274852671, 43242613716069407953, 1185802123987680144427, 35457442115448212075033, 990424779934371836605849

Offset: 0

Per H. Lundow

nonn

Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research report, No 12, 1996, Department of Math., Umea University, Sweden.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
Sergey Perepechko, Generation function
Index entries for linear recurrences with constant coefficients, signature (1, 1065, 2271, -313647, -581107, 42290089, 46394373, -3142067439, -1204065921, 141122117137, -23552838575, -4048343500561, 2177821303792, 77145898134992, -57692927620568, -1009771490156144, 834602390555152, 9348345877875672, -7534201668856784, -62671184060029400, 44881022619918032, 309385807529385808, -180904763263594728, -1136378367751634480, 495365037290693552, 3121850377815899650, -901764108815772034, -6426469969210271370, 1005943422942920850, 9913854106266511726, -456766693621948514, -11455967606609256194, -456766693621948514, 9913854106266511726, 1005943422942920850, -6426469969210271370, -901764108815772034, 3121850377815899650, 495365037290693552, -1136378367751634480, -180904763263594728, 309385807529385808, 44881022619918032, -62671184060029400, -7534201668856784, 9348345877875672, 834602390555152, -1009771490156144, -57692927620568, 77145898134992, 2177821303792, -4048343500561, -23552838575, 141122117137, -1204065921, -3142067439, 46394373, 42290089, -581107, -313647, 2271, 1065, 1, -1).

Row 12 of array A099390.

t[m_, n_] := Product[2*(2 + Cos[2*j*Pi/(m+1)] + Cos[2*k*Pi/(n+1)]), {k, 1, n/2}, {j, 1, m/2}]; a[n_] := N[t[n, 12], 16] // Round; Table[a[n], {n, 1, 15}] (* Jean-François Alcover, Dec 20 2012, after A099390 *)

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

A288026 Array read by antidiagonals: T(m,n) = number of maximal matchings in the grid graph P_m X P_n.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 2, 5, 5, 2, 3, 11, 22, 11, 3, 4, 24, 75, 75, 24, 4, 5, 51, 264, 400, 264, 51, 5, 7, 109, 941, 2357, 2357, 941, 109, 7, 9, 234, 3286, 13407, 22228, 13407, 3286, 234, 9, 12, 503, 11623, 76667, 207423, 207423, 76667, 11623, 503, 12

Offset: 1

Andrew Howroyd, Jun 04 2017

			Table starts:
=====================================================
m\n| 1   2    3     4       5        6          7
---|-------------------------------------------------
1  | 1   1    2     2       3        4          5 ...
2  | 1   2    5    11      24       51        109 ...
3  | 2   5   22    75     264      941       3286 ...
4  | 2  11   75   400    2357    13407      76667 ...
5  | 3  24  264  2357   22228   207423    1922112 ...
6  | 4  51  941 13407  207423  3136370   47256485 ...
7  | 5 109 3286 76667 1922112 47256485 1158560776 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..276
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set

Main diagonal is A287595.
Rows 1-3 are A182097(n+2), A286945, A288028.
Cf. A210662, A099390, A286912, A288025.

A028472 Number of perfect matchings in graph P_{10} X P_{n}.

Original entry on oeis.org

1, 1, 89, 571, 18061, 185921, 4213133, 53175517, 1031151241, 14479521761, 258584046368, 3852472573499, 65743732590821, 1012747193318519, 16848161392724969, 264499788583572499, 4337452956682508609, 68829675768134027209, 1119577238373960926141

Offset: 0

Per H. Lundow

nonn

J. L. Hock and R. B. McQuistan, A note on the occupational degeneracy for dimers on a saturated two-dimensional lattice space, Discrete Applied Mathematics, 1984, v.8, 101-104.
Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research report, No 12, 1996, Department of Math., Umea University, Sweden.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
Index entries for linear recurrences with constant coefficients, signature (1, 285, 411, -18027, -20689, 472275, 271027, -6149853, -471319, 42303393, -10402780, -157353820, 58545372, 335484428, -123321948, -429447820, 123321948, 335484428, -58545372, -157353820, 10402780, 42303393, 471319, -6149853, -271027, 472275, 20689, -18027, -411, 285, -1, -1).

Row 10 of array A099390.

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

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

G.f.: (1 - 197x^2 - 214x^3 + 9741x^4 + 7262x^5 - 202037x^6 - 56736x^7 + 2064705x^8 - 156848x^9 - 11058754x^10 + 2972710x^11 + 32425754x^12 - 10324398x^13 - 54699758x^14 + 15137114x^15 + 54699758x^16 - 10324398x^17 - 32425754x^18 + 2972710x^19 + 11058754x^20 - 156848x^21 - 2064705x^22 - 56736x^23 + 202037x^24 + 7262x^25 - 9741x^26 - 214x^27 + 197x^28 - x^30)/(1 - x - 285x^2 - 411x^3 + 18027x^4 + 20689x^5 - 472275x^6 - 271027x^7 + 6149853x^8 + 471319x^9 - 42303393x^10 + 10402780x^11 + 157353820x^12 - 58545372x^13 - 335484428x^14 + 123321948x^15 + 429447820x^16 - 123321948x^17 - 335484428x^18 + 58545372x^19 + 157353820x^20 - 10402780x^21 - 42303393x^22 - 471319x^23 + 6149853x^24 + 271027x^25 - 472275x^26 - 20689x^27 + 18027x^28 + 411x^29 - 285x^30 + x^31 + x^32). - Sergey Perepechko, Nov 27 2012

A189003 Number of domino tilings of the 5 X n grid with upper left corner removed iff n is odd.

Original entry on oeis.org

1, 1, 8, 15, 95, 192, 1183, 2415, 14824, 30305, 185921, 380160, 2332097, 4768673, 29253160, 59817135, 366944287, 750331584, 4602858719, 9411975375, 57737128904, 118061508289, 724240365697, 1480934568960, 9084693297025, 18576479568193, 113956161827912

Offset: 0

Alois P. Heinz, Apr 15 2011

Alois P. Heinz, Table of n, a(n) for n = 0..550
Index entries for sequences related to dominoes
Index entries for linear recurrences with constant coefficients, signature (0,15,0,-32,0,15,0,-1).

5th row of array A189006.

Bisections give: A003775 (even part), A006238 (odd part).

a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-1|15|-32|15>>^iquo(n, 2, 'r').
        `if`(r=0, <<8, 1, 1, 8>>, <<1, 0, 1, 15>>))[3, 1]:
seq(a(n), n=0..30);

a[n_] := Product[2(2+Cos[2 j Pi/(n+1)]+Cos[k Pi/3]), {k, 1, 2}, {j, 1, n/2} ] // Round;
Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Aug 19 2018, after A099390 *)

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

A287595 Number of maximal matchings in the n X n grid graph.

Original entry on oeis.org

1, 1, 2, 22, 400, 22228, 3136370, 1158560776, 1147204164108, 2980178704765860, 20513821200001569410, 373243563814532182524614, 17941038966060235808302667164

Offset: 0

Eric W. Weisstein, May 27 2017

Svenja Huntemann and Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set

Main diagonal of A288026.

Cf. A286945, A288028, A099390, A242861, A284703.

Join[{1}, Table[Length@FindIndependentVertexSet[LineGraph@GridGraph[{n, n}], Infinity, All], {n, 2, 6}]] (* Eric W. Weisstein, Jul 13 2024 *)

a(7)-a(10) from Andrey Zabolotskiy, May 31 2017
a(1) changed and a(0) prepended by Alois P. Heinz, May 31 2017
a(11)-a(12) from Andrew Howroyd, Jun 04 2017

cp's OEIS Frontend

A348452 Irregular triangle read by rows: T(n,k) (n >= 1, 1 <= k <= n^2) is the number of ways to tile an n X n chessboard with k rook-connected polyominoes of equal area.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A348453 Irregular triangle read by rows: T(n,k) (n >= 1, 1 <= k <= number of divisors of n^2) is the number of ways to tile an n X n chessboard with d_k rook-connected polyominoes of equal area, where d_k is the k-th divisor of n^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A360256 Number of ways to tile an n X n square using rectangles with distinct height X width dimensions.

Views

Author

Keywords

Comments

Examples

Crossrefs

A360498 Number of ways to tile an n X n square using oblongs with distinct dimensions.

Views

Author

Keywords

Comments

Examples

Crossrefs

A028473 Number of perfect matchings in graph P_{11} X P_{2n}.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A028474 Number of perfect matchings in graph P_{12} X P_{n}.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A288026 Array read by antidiagonals: T(m,n) = number of maximal matchings in the grid graph P_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

A028472 Number of perfect matchings in graph P_{10} X P_{n}.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A189003 Number of domino tilings of the 5 X n grid with upper left corner removed iff n is odd.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica