Abstract
In 2017, Duchi, Guerrini, Rinaldi and Schaeffer proposed new combinatorial objects called "fighting fish", which are counted by the same formula as more classical objects, such as two-stack sortable permutations and non-separable planar maps. In this article, we explore the bijective aspect of fighting fish by establishing a bijection to two-stack sortable permutations, using a new recursive decomposition of these permutations. With our bijection, we give combinatorial explanations of several results on fighting fish proved previously with generating functions. Using the decomposition, we also prove the algebraicity of a generating function of two-stack sortable permutations, extending a result of Bousquet-Mélou (1998).
| Original language | English |
|---|---|
| Title of host publication | Séminaire Lotharingien de Combinatoire |
| Subtitle of host publication | Proceedings of the 30th International Conference on "Formal Power Series and Algebraic Combinatorics" |
| Publisher | European Mathematical Society |
| Number of pages | 12 |
| Volume | 80B |
| ISBN (Electronic) | 1286-4889 |
| Publication status | Published - 1 Apr 2018 |
| Event | The 30th International Conference on Formal Power Series and Algebraic Combinatorics - Dartmouth college, Hanover, United States Duration: 16 Jul 2018 → 20 Jul 2018 https://sites.google.com/view/fpsac2018/home |
Conference
| Conference | The 30th International Conference on Formal Power Series and Algebraic Combinatorics |
|---|---|
| Abbreviated title | FPSAC 2018 |
| Country/Territory | United States |
| City | Hanover |
| Period | 16/07/18 → 20/07/18 |
| Internet address |
Keywords
- two-stack sortable permutations
- fighting fish
- bijection
- recursive decomposition