The OEIS is supported by the many generous donors to the OEIS Foundation.
%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