A291807 -id:A291807 - cp's OEIS frontend

A291806 The number of polyomino tilings of n X n square.

1, 5, 216, 212987

Offset: 1

John Mason, Sep 01 2017

The sequence gives the number of distinct tilings by polyominoes of a square with side n. As for "free" polyominoes, tilings that are reflections or rotations of each other are not considered distinct.

Using the same terminology used for polyominoes: the corresponding sequence for "fixed" tilings is 1,12,1434,1691690, and for one-sided tilings is 1,5,222,213315.

John Mason, Tiling examples

Cf. A268416 (polyominoes that will fit in n-sided square), A291807 (symmetric tilings), A291808 (tilings with distinct polyominoes), A291809 (tilings with differently sized polyominoes).

A363381 a(n) is the number of distinct n-cell patterns that tile an n X n square.

Original entry on oeis.org

1, 2, 1, 60, 1, 102, 1, 62714

Offset: 1

Thomas Young, May 30 2023

Consider n unit squares contained within an n X n square. The n unit squares are an n-cell pattern of the n X n square if, when copied n-1 times, they can, with various rigid transformations, be combined to tessellate the n X n square.
Put another way:
Consider, for example, for n = 4, a transparency with an outline of a 4 X 4 square filled by 16 unit squares. Any 4 unit squares are painted the same color. Those four squares are a potential n-cell pattern of the 4 X 4 square. Three copies of the transparency are made with only the color of the 4 squares being different. If a person can stack the transparencies in such a way that they fill the 4 X 4 square, then the n-cell pattern is acceptable.
Put another way:
n unit squares from an n X n square are painted a color. Those n unit squares are an n-cell pattern. If n-1 copies of the pattern can be painted (each a different color) and together they fill the n X n square, then the n unit squares form an acceptable n-cell pattern.
Conjecture by Andrew Young: For an n X n square, where n is an odd prime, there is only one n-cell pattern.
Conjecture by Andrew Young and Thomas Young: An odd integer n>=3 is prime iff there exists only one n-cell pattern for an n X n square.
For any number n, there is always the 1 X n pattern that tiles the n X n square.
For composite numbers n = f1*f2, 1 < f1 <= f2 < n, there is always an additional f1 X f2 pattern. For example, a 14 X 14 square can be tiled using fourteen 1 X 14 rectangles or fourteen 2 X 7 rectangles; a 15 X 15 square can be tiled using fifteen 1 X 15 rectangles or fifteen 3 X 5 rectangles; a 9 X 9 square can be tiled using nine 1 X 9 rectangles or nine 3 X 3 squares (as in Sudoku!).
The second conjecture is a Corollary of the first: If n = p*q is not prime, then there is always a second tiling using rectangles, as explained above. Since the second conjecture implies the first, the two conjectures are actually equivalent. - M. F. Hasler, Jun 15 2025

			For n = 1, there is one 1-cell pattern because there is only one unit square to paint.
For n = 2, there are two 2-cell patterns:
   +---+---+     +---+---+         +---+
   | 1 | 2 |     | 1 | 2 |         | 1 |
   +---+---+     +---+---+   and   +---+---+
   | 3 | 4 |                           | 4 |
   +---+---+                           +---+
For n = 3, there is one 3-cell pattern:
   +---+---+---+
   | 1 | 2 | 3 |
   +---+---+---+
   | 4 | 5 | 6 |     It is   +---+---+---+
   +---+---+---+             | 1 | 2 | 3 |
   | 7 | 8 | 9 |             +---+---+---+
   +---+---+---+
For n = 4, there are sixty 4-cell patterns:
   +---+---+---+---+
   | 1 | 2 | 3 | 4 |   One is  +---+---+---+---+
   +---+---+---+---+           | 1 | 2 | 3 | 4 |
   | 5 | 6 | 7 | 8 |           +---+---+---+---+
   +---+---+---+---+
   | 9 |10 |11 |12 |     which is equivalent to:
   +---+---+---+---+                       +---+
   |13 |14 |15 |16 |                       | 1 |
   +---+---+---+---+                       +---+
                                           | 5 |
                                           +---+
and therefore these two are not            | 9 |
counted as distinct patterns.              +---+
                                           |13 |
                                           +---+
Another 4-cell pattern for a 4 X 4 square
   +---+---+---+---+
   | x | x | y | y |
   +---+---+---+---+   is
   | z | y | x | a |          +---+---+
   +---+---+---+---+          | x | x |
   | y | z | a | x |          +---+---+---+
   +---+---+---+---+                  | x |
   | a | a | z | z |                  +---+---+
   +---+---+---+---+                      | x |
                                          +---+
     +---+---+
     | x | x |
     +---+---+---+       is equivalent to
             | x |
             +---+---+
                 | x |
                 +---+
           +---+---+  +---+                          +---+
           | y | y |  | z |                          | a |
       +---+---+---+  +---+---+                  +---+---+
       | y |              | z |                  | a |
   +---+---+              +---+---+---+  +---+---+---+
   | y |                      | z | z |  | a | a |
   +---+                      +---+---+  +---+---+
because the shapes can be created through reflection, rotation, or translation.
Therefore, they are counted as one pattern.
For n = 5, there is one 5-cell pattern.

Thomas Young, The 60 4-cell patterns for a 4 X 4 square.
Thomas Young, A Java program to calculate the number of 4-cell pattern for a 4 X 4 square.
Thomas Young, The 102 6-cell patterns for a 6 X 6 square.

Cf. A291806, A227004, A291808, A360630, A291807, A328020, A220778.

a(n) >= 2 if n is composite.

For n > 1, a(n) = 1 iff n is an odd prime (conjectured: cf comments).

a(7)-a(8) from Andrew Howroyd, Jun 04 2023

Minor edits by M. F. Hasler, Jun 15 2025

The sequence gives the number of distinct tilings by polyominoes of a square with side n, considering tilings that are formed of distinct polyominoes. As for "free" polyominoes, tilings that are reflections or rotations of each other are not considered distinct.

The sequence gives the number of distinct tilings by polyominoes of a square with side n, considering tilings that are formed by polyominoes of all different sizes. As for "free" polyominoes, tilings that are reflections or rotations of each other are not considered distinct.

cp's OEIS Frontend

A291806 The number of polyomino tilings of n X n square.

Views

Author

Keywords

Comments

Links

Crossrefs

A291808 Number of tilings of an n X n square using distinct polyominoes.

Views

Author

Keywords

Comments

Links

Crossrefs

A291809 Number of tilings of n X n square using differently sized polyominoes.

Views

Author

Keywords

Comments

Links

Crossrefs

A363381 a(n) is the number of distinct n-cell patterns that tile an n X n square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions