Further bijections to pattern-avoiding valid hook configurations

DOI10.1016/J.AAM.2020.102152zbMATH Open1461.05007arXiv1910.08895OpenAlexW3123604393MaRDI QIDQ2020016FDOQ2020016

Maya Sankar

Publication date: 23 April 2021

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

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.

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)

Cites Work

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

Cited In (8)

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

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)