login
A160911
a(n) is the number of arrangements of n square tiles with coprime sides in a rectangular frame, counting reflected, rotated or rearranged tilings only once.
3
1, 1, 2, 5, 11, 29, 84, 267, 921, 3481, 14322, 62306, 285845, 1362662, 6681508, 33483830
OFFSET
1,3
COMMENTS
There is only one arrangement of 1 square tile: a 1 X 1 rectangle. There is also only 1 arrangement of 2 square tiles: a 2 X 1 rectangle. There are 2 arrangements of 3 square tiles: a 3 X 1 rectangle (three 1 X 1 tiles) and a 3 X 2 rectangle (a 2 X 2 tile and two 1 X 1 tiles).
Short notation for the 2 possible 3-tile solutions:
3 X 1: 1,1,1
3 X 2: 2,1,1
More examples see below.
The smallest tile is not always a unit tile, e.g., one of the solutions for 5 tiles is: 6 X 5: 3,3,2,2,2.
My definition of a unique solution is the "signature" string in this notation: the rectangle size for nonsquares and the list of coprime tile sizes sorted largest to smallest. Rotations and reflections of a known solution are not new solutions; rearrangements of the same size tiles within the same overall boundary are not new solutions. But reorganizations of the same size tiles in different boundaries are unique solutions, such as 4 X 1: 1,1,1,1 and 2 X 2: 1,1,1,1.
From Rainer Rosenthal, Dec 23 2022: (Start)
The above description can be abbreviated as follows:
a(n) is the number of (2+n)-tuples (p X q: t_1,...,t_n) of positive integers, such that:
0. p >= q.
1. gcd(t_1,...,t_n) = 1 and t_i >= t_j for i < j and Sum_{i=1..n} t_i^2 = p * q.
2. Any p X q matrix is the disjoint union of contiguous t_i X t_i minors, i = 1..n. (For contiguous minors resp. submatrices see comments in A350237.)
.
The rectangle size p X q may have gcd(p,q) > 1, as seen in the examples for 3 X 2 and 6 X 4. Therefore a(n) >= A210517(n) for all n, and a(6) > A210517(6).
(End)
REFERENCES
See A002839 and A217156 for further references and links.
EXAMPLE
From Rainer Rosenthal, Dec 24 2022, updated May 09 2024: (Start)
.
|A|
|A B| |B|
|C D| (2 X 2: 1,1,1,1) |C| (4 X 1: 1,1,1,1)
|D|
.
|A A|
|A A A| |A A|
|A A A| |B B|
|A A A| (4 X 3: 3,1,1,1) |B B| (5 X 2: 2,2,1,1)
|B C D| |C D|
.
|A A A|
|A A A| <================= 3 X 3 minor A
|A A A| 2 X 2 minor B
|B B C| (5 X 3: 3,2,1,1) 1 X 1 minor C
|B B D| 1 X 1 minor D
________________________________________________________
a(4) = 5 illustrated as (p X q: t_1,t_2,t_3,t_4)
and as p X q matrices with t_i X t_i minors
.
Example configurations for a(6) = 29:
.
|A A A A|
|A A A A|
|A A A A|
|A A B| |A B| |A A A A|
|A A C| |C D| |B B C D|
|D E F| |E F| |B B E F|
______________________________________________
(3 X 3: (3 X 2: (6 X 4:
2,1,1,1,1,1) 1,1,1,1,1,1) 4,2,1,1,1,1)
. _________________________
|A A A A A A B B B B B B B| | | |
|A A A A A A B B B B B B B| | | |
|A A A A A A B B B B B B B| | 6 | |
|A A A A A A B B B B B B B| | | 7 |
|A A A A A A B B B B B B B| | | |
|A A A A A A B B B B B B B| |___________| |
|C C C C C D B B B B B B B| | |1|_____________|
|C C C C C E E E E F F F F| | | | |
|C C C C C E E E E F F F F| | 5 | 4 | 4 |
|C C C C C E E E E F F F F| | | | |
|C C C C C E E E E F F F F| |_________|_______|_______|
_____________________________ _____________________________
(13 X 11: 7,6,5,4,4,1) (13 X 11: 7,6,5,4,4,1)
[rotated by 90 degrees] [alternate visualization]
.(End)
KEYWORD
nonn,more
AUTHOR
Kevin Johnston, Feb 11 2016
EXTENSIONS
a(15)-a(16) from Kevin Johnston, Feb 11 2016
Title changed from Rainer Rosenthal, Dec 28 2022
STATUS
approved