Fighting fish and two-stack sortable permutations

MaRDI QIDQ2632714zbMATH OpenFDO

Authors W. Fang

Publication date 15 May 2019

Published in Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.05713, http://www.mat.univie.ac.at/~slc/wpapers/FPSAC2018//07-Fang.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

bijectionfighting fishrecursive decompositiontwo-stack sortable permutations

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15)

Abstract: In 2017, Duchi, Guerrini, Rinaldi and Schaeffer proposed a new family of 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 of two-stack sortable permutations, we also prove the algebraicity of their generating function, extending a result of Bousquet-M'elou (1998).

Recommendations

• On pattern-avoiding Fishburn permutations
• Permutations sortable by two stacks in series
• Stack-sortable permutations and beyond
• Multi-static enumeration of two-stack sortable permutations
• Fighting fish: enumerative properties
• Permutations sortable by deques and by two stacks in parallel
• Catalan and Schröder permutations sortable by two restricted stacks
• A survey of stack sortable permutations
• Sorted and/or sortable permutations

Cites work

• A bijective census of nonseparable planar maps
• A Census of Planar Maps
• A combinatorial proof of J. West's conjecture
• A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
• A trinity of duality: non-separable planar maps, \(\beta(1,0)\)-trees and synchronized intervals
• Enumeration of Non-Separable Planar Maps
• Fighting fish
• Fighting fish: enumerative properties
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• Left ternary trees and non-separable rooted planar maps
• Multi-static enumeration of two-stack sortable permutations
• On the Enumeration of Rooted Non-Separable Planar Maps
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
• Sorting twice through a stack
• The enumeration of generalized Tamari intervals
• The enumeration of generalized Tamari intervals

Cited in

(17)

• Fighting fish: enumerative properties
• Further bijections to pattern-avoiding valid hook configurations
• Troupes, cumulants, and stack-sorting
• Polyurethane toggles
• A structural characterisation of \(\mathrm{Av}(1324)\) and new bounds on its growth rate
• Stack-sorting preimages of permutation classes
• Counting 3-stack-sortable permutations
• Lattice paths and \((n - 2)\)-stack sortable permutations
• A bijection between Tamari intervals and extended fighting fish
• Stack-sorting for words
• Stack-sorting for Coxeter groups
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Bijections between fighting fish, planar maps, and Tamari intervals
• A direct bijection between two-stack sortable permutations and fighting fish (extended abstract)
• Combinatorics of rectangulations: old and new bijections
• A bijection between non-separable planar maps and fighting fish

This page was built for publication: Fighting fish and two-stack sortable permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2632714)