A360804 Number of ways to tile an n X n square using rectangles with distinct areas.

1, 1, 21, 253, 2401, 36237, 815929, 18713197

Offset: 1

Author

Scott R. Shannon, Feb 21 2023

Keywords

• nonn
• more

Comments

All possible tilings are counted, including those identical by symmetry. Note that distinct areas means that, for example, only one of the two rectangles with area 4, a 2 X 2 or 1 X 4 rectangle, can be used in any tiling.

Examples

			a(1) = 1 as the only way to tile a 1 X 1 square is with a square with dimensions 1 X 1.
a(2) = 1 as the only way to tile a 2 X 2 square is with a square with dimensions 2 X 2.
a(3) = 21. The possible tilings are the same as those given in the examples of A360499(3).
a(4) = 253. And example tiling of the 4 X 4 square is:
.
  +---+---+---+---+
  |   |       |   |
  +---+---+---+   +
  |           |   |
  +           +   +
  |           |   |
  +---+---+---+---+
  |               |
  +---+---+---+---+
.
which contains rectangles with areas 1, 2, 3, 4, 6. The one tiling, excluding symmetrically equivalent arrangements, that is excluded here but allowed in A360499 is:
.
  +---+---+---+---+
  |       |       |
  +       +       +
  |       |       |
  +---+---+       +
  |       |       |
  +---+---+---+---+
  |               |
  +---+---+---+---+
.
as this contains two rectangles with area 4. This can occur in 16 different ways so a(4) = A360499(4) - 16 = 269 - 16 = 253.
		

Crossrefs

Cf. A360499, A360498, A360725, A360256, A360773, A182275, A004003.