Séminaire Lotharingien de Combinatoire, 80B.7 (2018), 12 pp.
Wenjie Fang
Fighting Fish and Two-Stack Sortable Permutations
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).
Received: November 14, 2017.
Accepted: February 17, 2018.
Final version: April 1, 2018.
The following versions are available: