The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A363381 a(n) is the number of distinct n-cell patterns that tile an n X n square. 1
 1, 2, 1, 60, 1, 102, 1, 62714 (list; graph; refs; listen; history; text; internal format)
 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 28 22:38 EST 2023. Contains 367422 sequences. (Running on oeis4.)