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: