On the number of tilings of a square by rectangles

DOI10.1007/S00026-013-0209-2MaRDI QIDQ404384zbMATHOpenAlexFDO

Authors Tim Michaels, James Conant

Publication date 4 September 2014

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.5734

zbMATH Keywords

rectangular tilingsrectangulations

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Classification of homotopy type (55P15)

Abstract: We develop a recursive formula for counting the number of rectangulations of a square, i.e the number of combinatorially distinct tilings of a square by rectangles. Our formula specializes to give a formula counting generic rectangulations, as analyzed by Reading in [5]. Our computations agree with [5] as far as was calculated and extend to the non-generic case. An interesting feature of the number of rectangulations is that it appears to have an 8-fold periodicity modulo 2. We verify this periodicity for small values of n, but the general result remains elusive, perhaps hinting at some unseen structure on the space of rectangulations, analogous to Reading's discovery that generic rectangulations are in 1-1 correspondence with a certain class of permutations. Finally, we use discrete Morse theory to show that the space of tilings by less than or equal to n rectangles is homotopy-equivalent to a wedge of some number of (n-1)-dimensional spheres. Combined with formulae for the number of tilings, the exact homotopy type is computed for $nleq28$.

Recommendations

• Generic rectangulations
• scientific article; zbMATH DE number 1743835
• Tilings of rectangles with T-tetrominoes
• Counting colorful tilings of rectangular arrays
• Torus square tilings

Cites work

• scientific article; zbMATH DE number 51878 (Why is no real title available?)
• Characteristic Classes. (AM-76)
• Generic rectangulations
• Moduli of graphs and automorphisms of free groups
• Morse theory for cell complexes
• Perturbative series and the moduli space of Riemann surfaces
• The tropical Grassmannian

Cited in

(11)

• A note on perfect tilings of rectangles with rectangles
• Fourteen Proofs of a Result About Tiling a Rectangle
• scientific article; zbMATH DE number 7278010 (Why is no real title available?)
• Enumeration and asymptotic formulas for rectangular partitions of the hypercube
• Generic rectangulations
• On the enumeration of plane bipolar posets and transversal structures
• scientific article; zbMATH DE number 6670068 (Why is no real title available?)
• scientific article; zbMATH DE number 7298071 (Why is no real title available?)
• Combinatorial generation via permutation languages. III: Rectangulations
• scientific article; zbMATH DE number 1743835 (Why is no real title available?)
• scientific article; zbMATH DE number 1054784 (Why is no real title available?)

This page was built for publication: On the number of tilings of a square by rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404384)