Geodesic
Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations
Andrei Asinowski1 ; Gill Barequet2 ; Mireille Bousquet-Mélou3 ; Toufik Mansour4 ; Ron Y. Pinter5
1Technion - Israel Institute of Technology, and Freie Universität Berlin
2Technion - Israel Institute of Technology, and Tufts University
3LaBRI; Université de Bordeaux
4University of Haifa
5Technion - Israel Institute of Technology
The electronic journal of combinatorics, Tome 20 (2013) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/2607
Classification : 05A15, 05B45, 52C20
Mots-clés : floorplans, permutation patterns, Baxter permutations, guillotine floorplans, pattern avoiding permutations

Andrei Asinowski  1   ; Gill Barequet  2   ; Mireille Bousquet-Mélou  3   ; Toufik Mansour  4   ; Ron Y. Pinter  5

1 Technion - Israel Institute of Technology, and Freie Universität Berlin
2 Technion - Israel Institute of Technology, and Tufts University
3 LaBRI; Université de Bordeaux
4 University of Haifa
5 Technion - Israel Institute of Technology 
@article{10_37236_2607,
     author = {Andrei Asinowski and Gill Barequet and Mireille Bousquet-M\'elou and Toufik Mansour and Ron Y. Pinter},
     title = {Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {2},
     doi = {10.37236/2607},
     zbl = {1267.05018},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2607/}
}
TY  - JOUR
AU  - Andrei Asinowski
AU  - Gill Barequet
AU  - Mireille Bousquet-Mélou
AU  - Toufik Mansour
AU  - Ron Y. Pinter
TI  - Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2607/
DO  - 10.37236/2607
ID  - 10_37236_2607
ER  - 
%0 Journal Article
%A Andrei Asinowski
%A Gill Barequet
%A Mireille Bousquet-Mélou
%A Toufik Mansour
%A Ron Y. Pinter
%T Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2607/
%R 10.37236/2607
%F 10_37236_2607
Andrei Asinowski; Gill Barequet; Mireille Bousquet-Mélou; Toufik Mansour; Ron Y. Pinter. Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations. The electronic journal of combinatorics, Tome 20 (2013) no. 2. doi: 10.37236/2607

Cité par Sources :