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,2

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 composite numbers n, an n X n square will always have at least two n-cell patterns: a 1 X n pattern and an f1 X f2 pattern, where 1 < f1 <= f2 < n and f1*f2 = n. 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!).

For prime numbers p, a p X p square can always be tessellated with p rectangles that are 1 X p.

Links

Table of n, a(n) for n=1..8.

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.

Example

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 |
   +---+---+---+---+
   | 5 | 6 | 7 | 8 |  one is   +---+---+---+---+
   +---+---+---+---+           | 1 | 2 | 3 | 4 |
   | 9 |10 |11 |12 |           +---+---+---+---+
   +---+---+---+---+
   |13 |14 |15 |16 |
   +---+---+---+---+
   +---+---+---+---+                       +---+
   | 1 | 2 | 3 | 4 |  is equivalent to     | 1 |
   +---+---+---+---+                       +---+
                                           | 5 |
                                           +---+
                                           | 9 |
                                           +---+
                                           |13 |
                                           +---+
and therefore is counted as one pattern.
Another 4-cell pattern for a 4 X 4
   +---+---+---+---+
   | x | x | y | y |
   +---+---+---+---+
   | z | y | x | a |  is      +---+---+
   +---+---+---+---+          | 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.

Crossrefs

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

Sequence in context: A271442 A092650 A353586 * A221194 A309207 A104024

Adjacent sequences: A363378 A363379 A363380 * A363382 A363383 A363384

Keyword

nonn,more,hard

Author

Thomas Young, May 30 2023

Extensions

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

Status

approved