Fighting Fish and Two-Stack Sortable Permutations

Wenjie Fang

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


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 languageEnglish
Title of host publicationSéminaire Lotharingien de Combinatoire
Subtitle of host publicationProceedings of the 30th International Conference on "Formal Power Series and Algebraic Combinatorics"
PublisherEuropean Mathematical Society
Number of pages12
ISBN (Electronic)1286-4889
Publication statusPublished - 1 Apr 2018
EventThe 30th International Conference on Formal Power Series and Algebraic Combinatorics - Dartmouth college, Hanover, United States
Duration: 16 Jul 201820 Jul 2018


ConferenceThe 30th International Conference on Formal Power Series and Algebraic Combinatorics
Abbreviated titleFPSAC 2018
Country/TerritoryUnited States
Internet address


  • two-stack sortable permutations
  • fighting fish
  • bijection
  • recursive decomposition


Dive into the research topics of 'Fighting Fish and Two-Stack Sortable Permutations'. Together they form a unique fingerprint.

Cite this