Higher Dimensional Floorplans and Baxter $d$-Permutations

Abstract

A $2-$dimensional mosaic floorplan is a partition of a rectangle by other rectangles with no empty rooms. These partitions (considered up to some deformations) are known to be in bijection with Baxter permutations. A $d$-floorplan is the generalisation of mosaic floorplans in higher dimensions, and a $d$-permutation is a $(d-1)$-tuple of permutations. Recently, in N. Bonichon and P.-J. Morel,  J. Integer Sequences 25 (2022), Baxter $d$-permutations generalising the usual Baxter permutations were introduced.

In this paper, we consider mosaic floorplans in arbitrary dimensions, and we construct a generating tree for $d$-floorplans, which generalises the known generating tree structure for $2$-floorplans. The corresponding labels and rewriting rules appear to be significantly more involved in higher dimensions. Moreover we give a bijection between the $2^{d-1}$-floorplans and $d$-permutations characterized by forbidden vincular patterns. Surprisingly, this set of $d$-permutations is strictly contained within the set of Baxter $d$-permutations.