cp's OEIS Frontend

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

%I A340984 #31 Jun 18 2025 21:24:36
%S A340984 1,1,0,0,1,0,2,6,29,119,600
%N A340984 Number of prime rectangle tilings with n tiles up to equivalence.
%C A340984 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.
%C A340984 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.
%C A340984 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.
%H A340984 F. R. K. Chung, E. N. Gilbert, R. L. Graham, J. B. Shearer, and J. H. van Lint, <a href="https://mathweb.ucsd.edu/~ronspubs/82_04_tiling.pdf">Tiling Rectangles with Rectangles</a>, Mathematics Magazine, 1982.
%H A340984 Math StackExchange, <a href="https://math.stackexchange.com/questions/4008337/how-many-prime-rectangle-tilings-are-there">How many "prime" rectangle tilings are there?</a>
%H A340984 Benjamin D. Prins, <a href="/A340984/a340984.png">All tilings for n = 9, 10, 11</a>
%H A340984 Reddit, <a href="https://www.reddit.com/r/mathriddles/comments/bgilmu/distributing_a_rectangular_inheritance/">Distributing a rectangular inheritance</a>.
%e A340984 For n = 5 the a(5) = 1 example looks like
%e A340984    _____
%e A340984   | |___|
%e A340984   |_|_| |
%e A340984   |___|_|
%e A340984 .
%e A340984 For n = 7 the a(7) = 2 examples look like
%e A340984    _______    _______
%e A340984   | |_____|  |_____| |
%e A340984   |_|___| |  |___| | |
%e A340984   |   |_|_|  | |_|_|_|
%e A340984   |___|___|  |_|_____|
%Y A340984 Cf. A049021, A053740.
%K A340984 nonn,hard,more,nice
%O A340984 1,7
%A A340984 _Drake Thomas_, Feb 01 2021
%E A340984 a(9)-a(11) from _Benjamin D. Prins_, Jun 13 2025