A363381 - OEIS

%I #79 Jul 06 2023 09:35:58

%S 1,2,1,60,1,102,1,62714

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

%C 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.

%C Put another way:

%C 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.

%C Put another way:

%C 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.

%C Conjecture by Andrew Young:  For an n X n square, where n is an odd prime, there is only one n-cell pattern.

%C 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.

%C 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!).

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

%H Thomas Young, <a href="/A363381/a363381.pdf">The 60 4-cell patterns for a 4 X 4 square</a>.

%H Thomas Young, <a href="/A363381/a363381_1.txt">A Java program to calculate the number of 4-cell pattern for a 4 X 4 square</a>.

%H Thomas Young, <a href="/A363381/a363381_2.pdf">The 102 6-cell patterns for a 6 X 6 square</a>.

%e For n = 1, there is one 1-cell pattern because there is only one unit square to paint.

%e For n = 2, there are two 2-cell patterns:

%e    +---+---+     +---+---+         +---+

%e    | 1 | 2 |     | 1 | 2 |         | 1 |

%e    +---+---+     +---+---+   and   +---+---+

%e    | 3 | 4 |                           | 4 |

%e    +---+---+                           +---+

%e For n = 3, there is one 3-cell pattern:

%e    +---+---+---+

%e    | 1 | 2 | 3 |

%e    +---+---+---+

%e    | 4 | 5 | 6 |     it is   +---+---+---+

%e    +---+---+---+             | 1 | 2 | 3 |

%e    | 7 | 8 | 9 |             +---+---+---+

%e    +---+---+---+

%e For n  = 4, there are sixty 4-cell patterns:

%e    +---+---+---+---+

%e    | 1 | 2 | 3 | 4 |

%e    +---+---+---+---+

%e    | 5 | 6 | 7 | 8 |  one is   +---+---+---+---+

%e    +---+---+---+---+           | 1 | 2 | 3 | 4 |

%e    | 9 |10 |11 |12 |           +---+---+---+---+

%e    +---+---+---+---+

%e    |13 |14 |15 |16 |

%e    +---+---+---+---+

%e    +---+---+---+---+                       +---+

%e    | 1 | 2 | 3 | 4 |  is equivalent to     | 1 |

%e    +---+---+---+---+                       +---+

%e                                            | 5 |

%e                                            +---+

%e                                            | 9 |

%e                                            +---+

%e                                            |13 |

%e                                            +---+

%e and therefore is counted as one pattern.

%e Another 4-cell pattern for a 4 X 4

%e    +---+---+---+---+

%e    | x | x | y | y |

%e    +---+---+---+---+

%e    | z | y | x | a |  is      +---+---+

%e    +---+---+---+---+          | x | x |

%e    | y | z | a | x |          +---+---+---+

%e    +---+---+---+---+                  | x |

%e    | a | a | z | z |                  +---+---+

%e    +---+---+---+---+                      | x |

%e                                           +---+

%e      +---+---+

%e      | x | x |

%e      +---+---+---+       is equivalent to

%e              | x |

%e              +---+---+

%e                  | x |

%e                  +---+

%e            +---+---+  +---+                          +---+

%e            | y | y |  | z |                          | a |

%e        +---+---+---+  +---+---+                  +---+---+

%e        | y |              | z |                  | a |

%e    +---+---+              +---+---+---+  +---+---+---+

%e    | y |                      | z | z |  | a | a |

%e    +---+                      +---+---+  +---+---+

%e because the shapes can be created through reflection, rotation, or translation.

%e Therefore, they are counted as one pattern.

%e For n = 5, there is one 5-cell pattern.

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

%K nonn,more,hard

%O 1,2

%A _Thomas Young_, May 30 2023

%E a(7)-a(8) from _Andrew Howroyd_, Jun 04 2023