Orders induced by segments in floorplan partitions and (2-14-3,3-41-2)-avoiding permutations
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2010
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909572895080448 |
|---|---|
| author | Asinowski, Andrei Barequet, Gill Bousquet-Mélou, Mireille Mansour, Toufik Pinter, Ron |
| author_facet | Asinowski, Andrei Barequet, Gill Bousquet-Mélou, Mireille Mansour, Toufik Pinter, Ron |
| contents | A floorplan is a tiling of a rectangle by rectangles. There are natural ways to order the elements---rectangles and segments---of a floorplan. Ackerman, Barequet and Pinter studied a pair of orders induced by neighborhood relations between rectangles, and obtained a natural bijection between these pairs and (2-41-3, 3-14-2)-avoiding permutations, also known as (reduced) Baxter permutations. In the present paper, we first perform a similar study for a pair of orders induced by neighborhood relations between segments of a floorplan. We obtain a natural bijection between these pairs and another family of permutations, namely (2-14-3, 3-41-2)-avoiding permutations. Then, we investigate relations between the two kinds of pairs of orders---and, correspondingly, between (2-41-3, 3-14-2)- and (2-14-3, 3-41-2)-avoiding permutations. In particular, we prove that the superposition of both permutations gives a complete Baxter permutation (originally called w-admissible, by Baxter and Joichi in the sixties). In other words, (2-14-3, 3-41-2)-avoiding permutations are the hidden part of complete Baxter permutations. We enumerate these permutations. To our knowledge, the characterization of these permutations in terms of forbidden patterns and their enumeration are both new results. Finally, we also study the special case of the so-called guillotine floorplans. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1011_1889 |
| institution | arXiv |
| publishDate | 2010 |
| record_format | arxiv |
| spellingShingle | Orders induced by segments in floorplan partitions and (2-14-3,3-41-2)-avoiding permutations Asinowski, Andrei Barequet, Gill Bousquet-Mélou, Mireille Mansour, Toufik Pinter, Ron Combinatorics A floorplan is a tiling of a rectangle by rectangles. There are natural ways to order the elements---rectangles and segments---of a floorplan. Ackerman, Barequet and Pinter studied a pair of orders induced by neighborhood relations between rectangles, and obtained a natural bijection between these pairs and (2-41-3, 3-14-2)-avoiding permutations, also known as (reduced) Baxter permutations. In the present paper, we first perform a similar study for a pair of orders induced by neighborhood relations between segments of a floorplan. We obtain a natural bijection between these pairs and another family of permutations, namely (2-14-3, 3-41-2)-avoiding permutations. Then, we investigate relations between the two kinds of pairs of orders---and, correspondingly, between (2-41-3, 3-14-2)- and (2-14-3, 3-41-2)-avoiding permutations. In particular, we prove that the superposition of both permutations gives a complete Baxter permutation (originally called w-admissible, by Baxter and Joichi in the sixties). In other words, (2-14-3, 3-41-2)-avoiding permutations are the hidden part of complete Baxter permutations. We enumerate these permutations. To our knowledge, the characterization of these permutations in terms of forbidden patterns and their enumeration are both new results. Finally, we also study the special case of the so-called guillotine floorplans. |
| title | Orders induced by segments in floorplan partitions and (2-14-3,3-41-2)-avoiding permutations |
| topic | Combinatorics |
| url | https://arxiv.org/abs/1011.1889 |