A221844 -id:A221844 - cp's OEIS frontend

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

Kevin Johnston, Feb 11 2016

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)

			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)

See A002839 and A217156 for further references and links.

Stuart E. Anderson, Perfect Squared Rectangles and Squared Squares

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

a(15)-a(16) from Kevin Johnston, Feb 11 2016

Title changed from Rainer Rosenthal, Dec 28 2022

A221843 Number of partitions of n^2 into squares providing prime dissections of an n X n square into integer-sided squares.

Original entry on oeis.org

1, 1, 2, 5, 10, 27, 56, 141, 309, 742, 1558, 3808

Offset: 1

Geoffrey H. Morley, Jan 26 2013

In a prime dissection the GCD of the square sides is one.

			For n = 4 the a(4) = 5 sets of squares which provide prime dissections of a 4 X 4 square are {1(3 X 3), 7(1 X 1)}, {3(2 X 2), 4(1 X 1)}, {2(2 X 2), 8(1 X 1)}, {1(2 X 2), 12(1 X 1)} and {16(1 X 1)}.

Cf. A034295, A037444, A221844.

a(7) corrected and a(9)-a(12) from Alois P. Heinz, Apr 15 2013

A221845 Number of prime dissections of an n X n square into integer-sided squares.

Original entry on oeis.org

1, 1, 5, 38, 471, 10661, 450923, 35863932, 5353011030, 1500957421749, 790347882174803, 781621363452395224, 1451740730942350766747, 5064070747064013555843107, 33176273260130056822126522407

Offset: 1

Geoffrey H. Morley, Jan 26 2013

nonn

A dissection into squares was called prime by J. H. Conway in 1964 if the GCD of the sides of the squares is 1.

			For n = 3 the a(3) = 5 dissections are:
+-+-+-+   +-+-+-+   +-+-+-+   +-+---+   +---+-+
| | | |   | | | |   | | | |   | |   |   |   | |
+-+-+-+   +-+-+-+   +-+-+-+   +-+   |   |   +-+
| | | |   | |   |   |   | |   | |   |   |   | |
+-+-+-+   +-+   |   |   +-+   +-+-+-+   +-+-+-+
| | | |   | |   |   |   | |   | | | |   | | | |
+-+-+-+   +-+---+   +---+-+   +-+-+-+   +-+-+-+

J. H. Conway, Mrs Perkins's quilt, Proc. Camb. Phil. Soc., 60 (1964), 363-368.

Ed Wynn, Exhaustive generation of Mrs Perkins's quilt square dissections for low orders, arXiv:1308.5420

Cf. A045846, A221844.

Corrected and extended to a(15) by Geoffrey H. Morley, Feb 05 2013

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A221843 Number of partitions of n^2 into squares providing prime dissections of an n X n square into integer-sided squares.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A221845 Number of prime dissections of an n X n square into integer-sided squares.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions