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.

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.

Links

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

Stuart E. Anderson, Perfect Squared Rectangles and Squared Squares

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)

Crossrefs

Cf. A002839, A005670, A113881, A210517, A217156, A219924, A221843, A221844, A221845, A340726, A342558, A350237.

Sequence in context: A360810 A320171 A014211 * A092764 A237811 A264771

Adjacent sequences: A160908 A160909 A160910 * A160912 A160913 A160914

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