Bounds on the number of slicing, mosaic, and general floorplans

A floorplan can be defined as a rectangular dissection of the floorplan region. Simple and tight asymptotic bounds on the number of floorplans for different dissection structures help us to evaluate the size of the solution space of different floorplan representation. They are also interesting theoretically. However, only loose bounds exist in the literature. In this paper, we derive tighter asymptotic bounds on the number of slicing, mosaic and general floorplans. Consider the floorplanning of n blocks. For slicing floorplan, we prove that the exact number is n!((-1)ⁿ⁺¹/2)Σ_k=0ⁿ(3+√8)^n-2k(_k¹2/)(_{n - k}¹2/) and the tight bound is Θ(n!2^2.543n/n^1.5) [9] . For mosaic floorplan, we prove that the tight bound is Θ(n!2³ⁿ/n⁴). For general floorplan, we prove a tighter lower bound of Ω(n!2³ⁿ/n⁴) and a tighter upper bound of O(n!2⁵ⁿ/n^4.5).