A172477 -id:A172477 - 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.

A328020 Number of distinct tilings of an n X n square with free n-polyominoes.

Original entry on oeis.org

1, 1, 2, 22, 515, 56734, 19846102, 23437350133

Offset: 1

Jeff Bowermaster, Oct 01 2019

Jeff Bowermaster, Illustration of a(1)..a(4)
Jeff Bowermaster, Illustration of a(5)
Code Golf Stack Exchange, Number of distinct tilings of an n X n square with free n-polyominoes

Cf. A172477, A268427, A291806.

a(7) from Peter Kagey, Oct 10 2019, based on the Stack Exchange link.

a(8) from Christian Sievers, Oct 13 2019, based on the Stack Exchange link.

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

A167258 Number of ways to partition an n X 8 grid into 8 connected equal-area regions.

Original entry on oeis.org

1, 34, 1173, 40899, 1696781, 81459922, 3825111851, 187497290034

Offset: 1

R. H. Hardin Oct 31 2009

nonn

			Some solutions for n=3
...1.1.2.3.3.4.4.4...1.2.3.3.3.4.4.4...1.2.2.2.3.3.3.4...1.1.2.3.4.5.5.6
...1.2.2.5.3.6.6.7...1.2.5.6.6.7.8.8...1.1.5.5.6.7.7.4...1.2.2.3.4.5.7.6
...8.8.8.5.5.6.7.7...1.2.5.5.6.7.7.8...8.8.8.5.6.6.7.4...8.8.8.3.4.7.7.6
------
...1.2.2.2.3.3.4.4...1.1.2.3.3.4.5.5...1.1.2.2.3.4.5.5...1.1.1.2.3.3.3.4
...1.5.6.6.3.7.8.4...1.6.2.3.7.4.5.8...6.1.2.7.3.4.8.5...5.5.5.2.6.6.4.4
...1.5.5.6.7.7.8.8...6.6.2.7.7.4.8.8...6.6.7.7.3.4.8.8...7.7.7.2.6.8.8.8
------
...1.1.2.2.3.4.5.5...1.1.1.2.2.2.3.3...1.2.3.3.3.4.5.5...1.2.3.3.4.5.5.5
...1.6.2.7.3.4.8.5...4.4.4.5.6.6.3.7...1.2.2.6.6.4.7.5...1.2.3.6.4.7.7.8
...6.6.7.7.3.4.8.8...8.8.8.5.5.6.7.7...1.8.8.8.6.4.7.7...1.2.6.6.4.7.8.8
------
...1.2.3.4.4.5.6.6...1.1.2.3.4.4.5.6...1.1.2.3.3.3.4.4...1.1.2.2.2.3.4.4
...1.2.3.4.7.5.8.6...1.7.2.3.4.8.5.6...5.1.2.6.7.7.4.8...5.1.6.7.7.3.4.8
...1.2.3.7.7.5.8.8...7.7.2.3.8.8.5.6...5.5.2.6.6.7.8.8...5.5.6.6.7.3.8.8

Intersects with A172477. [From Johan de Ruiter, Feb 04 2010]

a(n) = A167264(n,8). - R. J. Mathar, Oct 13 2024

a(8) added by Johan de Ruiter, Feb 04 2010

A347581 The Barnyard sequence: a(n) is the minimum number of unit length line segments required to enclose areas of 1 through n on a square grid.

Original entry on oeis.org

4, 9, 14, 20, 26, 33, 40, 47, 55, 63

Offset: 1

Scott R. Shannon, Oct 05 2021

The areas of size 1 through n can be created in any order and position, the only requirement being the final number of line segments used to enclose all areas is minimized. It is likely the perimeter of each area of size k, 1 <= k <= n, is the minimum possible for an area of size k, although this is unknown.

See A348149 for the total segments when the number of segments at each step is minimized.

			Example areas using the minimum number of line segments from n = 1 through n = 10 are:
.
   __
  |__|  a(1) = 4
   __ __ __
  |__|__ __|  a(2) = 9
   __ __ __
  |__|__ __|  a(3) = 14
  |__ __ __|
   __ __ __
  |__|__ __|
  |__ __ __|  a(4) = 20
  |     |
  |__ __|
   __ __ __
  |__|__ __|__
  |__ __ __|  |  a(5) = 26
  |     |     |
  |__ __|__ __|
   __ __ __
  |__|__ __|__ __ __
  |__ __ __|  |     |  a(6) = 33
  |     |     |     |
  |__ __|__ __|__ __|
         __ __ __ __
   __ __|__         |
  |__|__ __|__ __ __|
  |__ __ __|  |     |  a(7) = 40
  |     |     |     |
  |__ __|__ __|__ __|
   __ __ __ __ __ __
  |           |     |
  |__ __ __ __|     |
  |        |__ __ __|   a(8) = 47
  |__ __ __|__      |
  |     |  |  |__ __|
  |__ __|__|__ __|__|
   __ __ __ __ __ __ __
  |        |           |
  |        |__ __ __ __|
  |__ __ __|__         |
     |__|__ __|__ __ __|  a(9) = 55
     |__ __ __|  |     |
     |     |     |     |
     |__ __|__ __|__ __|
   __ __ __ __ __ __ __ __
  |         __|__   |     |
  |__ __ __|     |__|__   |
  |        |     |     |__|
  |        |     |     |  |   a(10) = 63
  |__ __ __|__ __|__ __|__|
  |              |     |__|
  |__ __ __ __ __|__ __|
.

Sascha Kurz, Counting polyominoes with minimum perimeter, arXiv:math/0506428 [math.CO], 2015.

Cf. A348149, A001168, A291808, A291809, A328020, A291806, A172477, A006983.

A365271 Minimum number of shaded squares needed on an n X n grid divided into rectangular regions so that more than half of the regions have more than half of their squares shaded and the area of the smallest region is more than half that of the largest region.

Original entry on oeis.org

1, 3, 4, 6, 8, 11, 14, 16, 20, 24, 28, 32, 36, 42, 48, 54, 60, 66, 72, 80, 88, 96, 104, 112, 120, 130, 140, 150, 158, 168, 180, 192, 204, 215, 226, 238, 252, 264, 277, 289, 306, 320, 336, 351

Offset: 1

Andrew Parkinson, Aug 30 2023

Developed from the Destroying Democracy Puzzle created by Gordon Hamilton.

To achieve a minimum, we need there to be x regions of area >= 2m-1 and (x-1) regions of area <= 4m-3 and m squares shaded in each of the x smaller regions. It can be shown that it is sufficient to only consider an odd number (2x-1) of regions. A weak lower bound is given in the formula section. Exhaustive searches lead to a stronger lower bound on each term, a(n), by identifying values of x and m which enable us to apportion the n^2 grid squares into rectangular regions with side lengths <= n. We then confirm each term by finding an actual configuration of regions that fits the n X n grid.

			For n=4, a(4)=6:
.
              +-----------+---+
  Region A -->| X   X   O | O |
              +-----------+   |
  Region B -->| X   X   O | O |
              +-----------+   |<-- Region E
  Region C -->| X   X   O | O |
              +-----------+   |
  Region D -->| O   O   O | O |
              +-----------+---+
.
The diagram shows the 4 X 4 grid divided into 5 regions. In the 3 regions A, B and C (more than half of the regions), more than half of the squares within each region (2 out of 3) are shaded (X). Of the 16 squares, only 6 (the minimum possible) are shaded; therefore, a(4)=6.
See the Hamilton link for more examples.

Gordon Hamilton, Destroying Democracy!, MathPickle, 2020.
Andrew Parkinson and Rob Pratt, Additional and conjectured terms to a(61).

Cf. A341319, A172477.

A weak lower bound on a(n) is a(n) > n^2/6. (The area of the smaller regions with more than half of their squares shaded is more than half of the area of the larger regions, so the area of the smaller regions is more than one third of the total grid; therefore the number of shaded squares is greater than one sixth of the number of grid squares.)

a(29)-a(44) obtained via integer linear programming by Rob Pratt, Jul 26 2024

A172478 The number of ways to dissect an n X n square into polyominoes of size n and then fill it to make it a Latin square, with the extra requirement that each number occurs within each polyomino exactly once.

Original entry on oeis.org

1, 4, 72, 13872, 11762160, 234312972480, 41182101508222080

Offset: 1

Johan de Ruiter, Feb 04 2010

nonn

a(n) is the number of completed n X n jigsaw sudoku puzzles.

			A 2 X 2 square can be covered by two dominoes by either positioning them vertically or horizontally. Both of these coverings allow for two 2 X 2 Latin squares without violating the extra constraint.

J. de Ruiter, On Jigsaw Sudoku Puzzles and Related Topics, Bachelor Thesis, Leiden Institute of Advanced Computer Science, 2010. [From Johan de Ruiter, Jun 15 2010]

Cf. A002860 (Number of Latin squares of order n), A172477 (Number of ways to dissect an n X n square into polyominoes of size n).

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

A328020 Number of distinct tilings of an n X n square with free n-polyominoes.

Views

Author

Keywords

Links

Crossrefs

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

A167258 Number of ways to partition an n X 8 grid into 8 connected equal-area regions.

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions

A347581 The Barnyard sequence: a(n) is the minimum number of unit length line segments required to enclose areas of 1 through n on a square grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A365271 Minimum number of shaded squares needed on an n X n grid divided into rectangular regions so that more than half of the regions have more than half of their squares shaded and the area of the smallest region is more than half that of the largest region.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A172478 The number of ways to dissect an n X n square into polyominoes of size n and then fill it to make it a Latin square, with the extra requirement that each number occurs within each polyomino exactly once.

Views

Author

Keywords

Comments

Examples

References

Crossrefs