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

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

Offset: 1

Author

Thomas Young, May 30 2023

Keywords

• nonn
• more
• hard

Comments

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

Examples

			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.
		

Links

• 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.

Crossrefs

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

Formula

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

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

Extensions

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

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