Further bijections to pattern-avoiding valid hook configurations

DOI10.1016/J.AAM.2020.102152MaRDI QIDQ2020016zbMATH OpenOpenAlexFDO

Authors Maya Sankar

Publication date 23 April 2021

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.08895

zbMATH Keywords

Motzkin pathsMotzkin posetsWest's stack-sorting map

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics of partially ordered sets (06A07)

Abstract: Valid hook configurations are combinatorial objects used to understand West's stack-sorting map. We extend existing bijections corresponding valid hook configurations to intervals in partial orders on Motzkin paths. To enumerate valid hook configurations on $312$-avoiding permutations, we build off of an existing bijection into a Motzkin poset and construct a bijection to certain well-studied closed lattice walks in the first quadrant. We use existing results about these lattice paths to show that valid hook configurations on $312$-avoiding permutations are not counted by a $D$-finite generating function, resolving a question of Defant's, and additionally to compute asymptotics for the number of such configurations. We also extend a bijection of Defant's to a correspondence between valid hook configurations on $132$-avoiding permutations and intervals in the Motzkin-Tamari posets, providing a more elegant proof of Defant's enumeration thereof. To investigate this bijection, we present a number of lemmas about valid hook configurations that are generally applicable and further study the bijections of Defant's.

Recommendations

• 312-Avoiding reduced valid hook configurations and duck words
• Stack-sorting preimages of permutation classes
• Stack-sorting, set partitions, and Lassalle's sequence
• On the diagram of 132-avoiding permutations
• Classification of bijections between 321- and 132-avoiding permutations

Cites work

• A partial order on Motzkin paths
• 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 survey of stack-sorting disciplines
• Catalan intervals and uniquely sorted permutations
• Chain lengths in the Tamari lattice
• Combinatorics of permutations
• Cubic realizations of Tamari interval lattices
• Cumulants of the q-semicircular law, Tutte polynomials, and heaps
• Descents in t-sorted permutations
• Enumerating, Ranking and Unranking Binary Trees
• Fertility numbers
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Fighting fish and two-stack sortable permutations
• scientific article; zbMATH DE number 3178652 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• Intervals in Catalan lattices and realizers of triangulations
• Lattice paths and pattern-avoiding uniquely sorted permutations
• Lattices of lattice paths
• Multi-static enumeration of two-stack sortable permutations
• Non-D-finite excursions in the quarter plane
• On a subposet of the Tamari lattice
• On Tamari lattices
• Permutation patterns and statistics
• Polyurethane toggles
• Postorder Preimages
• Preimages under the stack-sorting algorithm
• Problems of associativity: a simple proof for the lattice property of systems ordered by a semi-associative law
• Random walks in cones
• Realization of the Stasheff polytope
• Sorted and/or sortable permutations
• Stack-sorting preimages of permutation classes
• Stack-sorting, set partitions, and Lassalle's sequence

Cited in

(8)

• Stack-sorting with consecutive-pattern-avoiding stacks
• Troupes, cumulants, and stack-sorting
• Counting 3-stack-sortable permutations
• Stack-sorting for words
• 312-Avoiding reduced valid hook configurations and duck words
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Fertilitopes
• Stack-sorting, set partitions, and Lassalle's sequence

This page was built for publication: Further bijections to pattern-avoiding valid hook configurations

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