A340984 Number of prime rectangle tilings with n tiles up to equivalence.

1, 1, 0, 0, 1, 0, 2, 6, 29, 119, 600

Offset

1,7

Comments

Say that a tiling of a rectangle by other rectangles is prime if the only sub-rectangles in the tiling are those formed by a single tile. Say that two tilings are equivalent if there exists an inclusion/overlap-preserving bijection between the vertices, edges, and faces of every rectangle in them.

Problem 69 in Hugo Steinhaus's One Hundred Problems In Elementary Mathematics asks the reader to show that a(3) = a(4) = 0, and that there exist prime dissections for 5, 7, and 8 in which the pieces are of equal area. It cites Czesław Ryll-Nardzewski as proving that a(6) = 0, though this is not difficult to show by hand. The book also provides diagrams of both n = 7 solutions and four of the six n = 8 solutions.

Chung et al.'s paper Tiling Rectangles with Rectangles shows that the sequence grows at least as fast as c*2^(n/7) for some positive constant c, and states without proof that it is bounded above by 20000^n.

Links

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

F. R. K. Chung, E. N. Gilbert, R. L. Graham, J. B. Shearer, and J. H. van Lint, Tiling Rectangles with Rectangles, Mathematics Magazine, 1982.

Math StackExchange, How many "prime" rectangle tilings are there?

Benjamin D. Prins, All tilings for n = 9, 10, 11

Reddit, Distributing a rectangular inheritance.

Example

For n = 5 the a(5) = 1 example looks like
   _____
  | |___|
  |_|_| |
  |___|_|
.
For n = 7 the a(7) = 2 examples look like
   _______    _______
  | |_____|  |_____| |
  |_|___| |  |___| | |
  |   |_|_|  | |_|_|_|
  |___|___|  |_|_____|

Crossrefs

Cf. A049021, A053740.

Sequence in context: A368003 A368143 A284594 * A027109 A348764 A372372

Adjacent sequences: A340981 A340982 A340983 * A340985 A340986 A340987

Keyword

nonn,hard,more,nice

Author

Drake Thomas, Feb 01 2021

Extensions

a(9)-a(11) from Benjamin D. Prins, Jun 13 2025

Status

approved