A direct bijection between two-stack sortable permutations and fighting fish

EUROCOMB’23

Abstract
We define a bijection between two-stack sortable permutations and fighting fish, enriching the garden of bijections linking the numerous combinatorial classes counted by the sequence $A000139$ of the OEIS. Our bijection is (up to symmetry) the non-recursive version of the one of Fang (2018). Along the way, we encounter labeled sorting trees, a new class of trees that appear to have nice properties that seem worth to explore.

Pages:
283–289
References

M. Bousquet-Mélou. Multi-statistic enumeration of two-stack sortable permutations. The Electronic Journal of Combinatorics, 5(1):R21, 1998.
https://doi.org/10.37236/1359

E. Duchi, V. Guerrini, S. Rinaldi, and G. Schaeffer. Fighting Fish. Journal of Physics A : Mathematical and Theoretical, 50.2, 2016.
https://doi.org/10.1088/1751-8121/50/2/024002

E. Duchi, V. Guerrini, S. Rinaldi, and G. Schaeffer. Fighting Fish: Enumerative Properties. In 29th International Conference on "Formal Power Series and Algebraic Combinatorics" (FPSAC 2017). Séminaire Lotharingien de Combinatoire 78B.43, 2017.

E. Duchi and C. Henriet. A bijection between rooted planar maps and generalized fighting fish, 2022.
https://doi.org/10.1016/j.ejc.2023.103698

E. Duchi and C. Henriet. A bijection between Tamari intervals and extended fighting fish. European Journal of Combinatorics, 110:103698, 2023.
https://doi.org/10.1016/j.ejc.2023.103698

S. Dulucq, S. Gire, and O. Guibert. A combinatorial proof of J. West's conjecture. Discrete Mathematics, 187(1):71-96, 1998.
https://doi.org/10.1016/S0012-365X(98)80005-8

W. Fang. Fighting Fish and Two-Stack Sortable Permutations. In 30th International Conference on "Formal Power Series and Algebraic Combinatorics" (FPSAC 2018). Séminaire Lotharingien de Combinatoire 80B.7, 2018.

I. P. Goulden and J. West. Raney Paths and a Combinatorial Relationship between Rooted Nonseparable Planar Maps and Two-Stack-Sortable Permutations. Journal of Combinatorial Theory, Series A, 75(2):220-242, 1996.
https://doi.org/10.1006/jcta.1996.0074

D. E. Knuth. The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass., third edition, 1997.

OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences. Published electronically at http://oeis.org.

J. West. Sorting twice through a stack. Theoretical Computer Science, 117(1):303-313, 1993.
https://doi.org/10.1016/0304-3975(93)90321-J

D. Zeilberger. 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)!). Discrete Mathematics, 102(1):85-93, 1992.
https://doi.org/10.1016/0012-365X(92)90351-F

Metrics

0

Views

0

PDF views