A227690 -id:A227690 - cp's OEIS frontend

A224239 Number of inequivalent ways to cut an n X n square into squares with integer sides.

1, 2, 3, 13, 77, 1494, 56978, 4495023, 669203528, 187623057932, 98793520541768, 97702673827558670

Offset: 1

N. J. A. Sloane, Apr 15 2013

Similar to A045846, but now we do not regard dissections which differ by a rotation and/or reflection as distinct.

			For n=5, the illustrations (see links) show that the 77 solutions consist of:
4 dissections each with 1 image under the group of the square, for a total of 4,
2 dissections each with 2 images under the group of the square, totaling 4,
26 dissections each with 4 images under the group of the square, totaling 104, and
45 dissections each with 8 images under the group of the square, totaling 360,
for a grand total of 77 dissections with 472 images, agreeing with A045846(5) = 472.

Don Reble, C programs for A224239
Don Reble, Comments on the calculation of a(10)
N. J. A. Sloane, Illustration of the first five terms, page 1 of 4 (Each dissection is labeled with the number of its images under the symmetry group of the square. The sum of these numbers is A045846(n).)
N. J. A. Sloane, Illustration of the first five terms, page 2 of 4 (The largest squares are drawn in red. The next-largest squares, unless of size 1, are drawn in blue.)
N. J. A. Sloane, Illustration of the first five terms, page 3 of 4 (The largest squares are drawn in red. The next-largest squares, unless of size 1, are drawn in blue.)
N. J. A. Sloane, Illustration of the first five terms, page 4 of 4 (The largest squares are drawn in red. The next-largest squares, unless of size 1, are drawn in blue.)
Ed Wynn, Exhaustive generation of Mrs Perkins's quilt square dissections for low orders, 2013; arXiv:1308.5420

Main diagonal of A227690.

Cf. A045846, A034295, A219924.

a(6)-a(10) from Don Reble, Apr 15 2013

a(11)-a(12) from Ed Wynn, 2013. - N. J. A. Sloane, Nov 29 2013

A359019 Number of inequivalent tilings of a 3 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 21, 39, 82, 163, 347, 717, 1533, 3232, 6927, 14748, 31645, 67690, 145322, 311535, 668997, 1435645, 3083301, 6619842, 14218066, 30533005, 65580338, 140847132, 302522253, 649759735, 1395611508, 2997573501, 6438470626, 13829057884, 29703388721, 63799607283, 137035047576, 294336860797, 632205714741

Offset: 0

John Mason, Dec 12 2022

nonn

			a(4) is 6 because of:
  +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
  | | | | |     | |   | | |   | | |   | | | | | |
  +-+-+-+ +     + +   +-+ +   +-+ +   +-+ +-+-+-+
  | | | | |     | |   | | |   | | |   | | |   | |
  +-+-+-+ +     + +-+-+-+ +-+-+-+ +-+-+-+ +   +-+
  | | | | |     | |   | | | |   | | | | | |   | |
  +-+-+-+ +-+-+-+ +   +-+ +-+   + +-+-+-+ +-+-+-+
  | | | | |     | |   | | | |   | | | | | | | | |
  +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+

John Mason, Table of n, a(n) for n = 0..1000
John Mason, Counting free tilings of a rectangle

Column k = 3 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.
Cf. A000930.

For n <= 1, a(n)=1;
otherwise for odd n > 1, a(n)=(A002478(n) + A000930(n) + 2 * A002478((n - 1) / 2) + 2 * A002478((n - 3) / 2)) / 4
and for even n, a(n)=(A002478(n) + A000930(n) + 2 * A002478((n - 2) / 2) + 2 * A002478(n / 2)) / 4
Alternatively, from Walter Trump:
For n <= 1, a(n)=1;
otherwise for odd n > 1, a(n)=(A000930(2n) + A000930(n) + 2 * A000930(n - 1) + 2 * A000930(n - 3)) / 4
and for even n, a(n)=(A000930(2n) + 2 * A000930(n - 2) + 3 * A000930(n)) / 4

A359020 Number of inequivalent tilings of a 4 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 4, 6, 13, 39, 115, 295, 861, 2403, 7048, 20377, 60008, 175978, 519589, 1532455, 4531277, 13395656, 39639758, 117301153, 347248981, 1028011708, 3043852214, 9012879842, 26689014028, 79033362580, 234045889421, 693101137571, 2052569508948

Offset: 0

John Mason, Dec 12 2022

nonn

			a(3) is 6 because of:
  +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
  | | | | |     | |   | | |   | | |   | | | | | |
  +-+-+-+ +     + +   +-+ +   +-+ +   +-+ +-+-+-+
  | | | | |     | |   | | |   | | |   | | |   | |
  +-+-+-+ +     + +-+-+-+ +-+-+-+ +-+-+-+ +   +-+
  | | | | |     | |   | | | |   | | | | | |   | |
  +-+-+-+ +-+-+-+ +   +-+ +-+   + +-+-+-+ +-+-+-+
  | | | | |     | |   | | | |   | | | | | | | | |
  +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+

John Mason, Table of n, a(n) for n = 0..1000
John Mason, Counting free tilings of a rectangle

Column k = 4 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

For even n > 4
a(n) = (A054856(n) + compo(n) + 4 * A054856((n - 2) / 2) +
2 * A054856((n - 4) / 2) + 2 * A054856(n / 2) +
2 * Sum_{k=0..(n - 2) / 2} (A054856(k))) / 4
For odd n > 4
a(n) = (A054856(n) + compo(n) + 2 * A054856((n - 3) / 2) +
2 * A054856((n - 1) / 2) + 2 * Sum_ {k=0..(n - 3) / 2} (A054856(k))) / 4
Where compo(n) is the number of distinct compositions of n as a sum of 1, 2, (1+1) and 4.

A359021 Number of inequivalent tilings of a 5 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 5, 10, 39, 77, 521, 1985, 8038, 32097, 130125, 525676, 2131557, 8635656, 35017970, 141968455, 575692056, 2334344849, 9465939422, 38384559168, 155652202456, 631178976378, 2559476952229, 10378857744374, 42087027204278, 170665938023137, 692062856184512

Offset: 0

John Mason, Dec 12 2022

nonn

			a(2) is 5 because of:
  +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
  | | | |   | |   | |   | |   |
  +-+-+ +-+-+ +   + +   + +-+-+
  | | | |   | |   | |   | |   |
  +-+-+ +   + +-+-+ +-+-+ +   +
  | | | |   | |   | | | | |   |
  +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
  | | | |   | |   | | | | | | |
  +-+-+ +   + +   + +-+-+ +-+-+
  | | | |   | |   | | | | | | |
  +-+-+ +-+-+ +-+-+ +-+-+ +-+-+

John Mason, Table of n, a(n) for n = 0..1000
John Mason, Counting tilings of width 5 rectangles

Column k = 5 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.
Cf. A079975.

For even n > 5:
a(n) = (A054857(n) + A079975(n) + 2*A054857(n/2) + 2* fixed_md(n/2) + 2*A054857((n-4)/2) + 4*A054857((n-2)/2) + 2* (A054857((n/2)-1) + fixed_md((n/2)-1)))/4.
For odd n > 5:
a(n) = (A054857(n) + A079975(n) + 2*A054857((n-1)/2) + 4*A054857((n-3)/2) + 2*fixed_md((n-3)/2) + 2*A054857((n-5)/2) + 2*fixed_md((n-1)/2))/4.
where
fixed_md(1)=1, fixed_md(2)=3, fixed_md(3)=15 and for n > 3, fixed_md(n) = A054857(n-1) + A054857(n-2) + fixed_md(n-2)+ fixed_md(n-1) + 2*A054857(n-3) + fixed_md(n-3).

A359022 Number of inequivalent tilings of a 6 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 9, 21, 115, 521, 1494, 15129, 83609, 459957, 2551794, 14150081, 78597739

Offset: 0

John Mason, Dec 12 2022

Column k = 6 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

A359023 Number of inequivalent tilings of a 7 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 12, 39, 295, 1985, 15129, 56978, 861159, 6542578, 49828415

Offset: 0

John Mason, Dec 12 2022

Column k = 7 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

A359024 Number of inequivalent tilings of an 8 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 21, 82, 861, 8038, 83609, 861159, 4495023

Offset: 0

John Mason, Dec 12 2022

Column k = 8 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

A359025 Number of inequivalent tilings of a 9 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 30, 163, 2403, 32097, 459957, 6542578, 93604244

Offset: 0

John Mason, Dec 12 2022

Column k = 9 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

A359026 Number of inequivalent tilings of a 10 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 51, 347, 7048, 130125, 2551794, 49828415

Offset: 0

John Mason, Dec 12 2022

Column k = 10 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

A362258 Triangle read by rows: T(n,k) is the maximum number of ways in which a set of integer-sided squares can tile an n X k rectangle, up to rotations and reflections, 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4, 1, 1, 2, 4, 13, 20, 1, 1, 4, 8, 33, 125, 277, 1, 1, 6, 12, 72, 403, 2505, 7855, 1, 1, 9, 22, 204, 1438, 12069, 101587, 487662

Offset: 0

Pontus von Brömssen, Apr 15 2023

			Triangle begins:
  n\k| 0  1  2  3   4    5     6      7      8
  ---+----------------------------------------
  0  | 1
  1  | 1  1
  2  | 1  1  1
  3  | 1  1  1  1
  4  | 1  1  2  2   4
  5  | 1  1  2  4  13   20
  6  | 1  1  4  8  33  125   277
  7  | 1  1  6 12  72  403  2505   7855
  8  | 1  1  9 22 204 1438 12069 101587 487662
See A362142 for an illustration of T(5,4) = 13.
The following table shows which sets of squares can tile the n X k rectangle in T(n,k) ways. A list x_1, ..., x_j represents a set of x_1 squares of side 1, ..., x_j squares of side j. When there are multiple solutions they are shown on separate lines. For (n,k) = (4,3), for example, the maximum number T(4,3) = 2 of tilings is obtained both for the set of 8 squares of side 1 and 1 square of side 2, and for the set of 4 squares of side 1 and 2 squares of side 2.
  n\k| 1   2      3     4     5     6      7       8
  ---+------------------------------------------------
  1  | 1
  2  | 2  4
     |    0,1
  3  | 3  6     9
     |    2,1   5,1
     |          0,0,1
  4  | 4  4,1   8,1    8,2
     |          4,2
  5  | 5  6,1   7,2   12,2  13,3
     |    2,2
  6  | 6  4,2  10,2   12,3  14,4  20,4
  7  | 7  6,2  13,2   12,4  19,4  22,5  25,6
  8  | 8  8,2  12,3   16,4  20,5  24,6  23,6,1  27,7,1

Main diagonal: A362259.
Columns: A000012 (k = 0,1), A362260 (k = 2), A362261 (k = 3), A362262 (k = 4), A362263 (k = 5).
Cf. A227690, A361221 (rectangular pieces), A362142.

T(n,k) >= A362142(n,k)/4 if n != k.

T(n,n) >= A362142(n,n)/8.

cp's OEIS Frontend

A224239 Number of inequivalent ways to cut an n X n square into squares with integer sides.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A359019 Number of inequivalent tilings of a 3 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A359020 Number of inequivalent tilings of a 4 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A359021 Number of inequivalent tilings of a 5 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A359022 Number of inequivalent tilings of a 6 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Crossrefs

A359023 Number of inequivalent tilings of a 7 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Crossrefs

A359024 Number of inequivalent tilings of an 8 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Crossrefs

A359025 Number of inequivalent tilings of a 9 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Crossrefs

A359026 Number of inequivalent tilings of a 10 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Crossrefs

A362258 Triangle read by rows: T(n,k) is the maximum number of ways in which a set of integer-sided squares can tile an n X k rectangle, up to rotations and reflections, 0 <= k <= n.

Views

Author

Keywords

Examples

Crossrefs

Formula