Catalan intervals and uniquely sorted permutations

DOI10.1016/J.JCTA.2020.105250MaRDI QIDQ2174949zbMATH OpenOpenAlexFDO

Authors Colin Defant

Publication date 27 April 2020

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

Dyck pathnoncrossing partition latticePallo comb posetposet intervalstack-sortingStanley latticeTamari latticeuniquely sorted permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: For each positive integer $k$, we consider five well-studied posets defined on the set of Dyck paths of semilength $k$. We prove that uniquely sorted permutations avoiding various patterns are equinumerous with intervals in these posets. While most of our proofs are bijective, some use generating trees and generating functions. We end with several conjectures.

Recommendations

• Catalan and Schröder permutations sortable by two restricted stacks
• A partition of Catalan permuted sequences with applications
• Interval posets of permutations
• Sequences of ordered sets and Catalan numbers
• From Motzkin to Catalan permutations
• Restricted permutations from Catalan to Fine and back
• On Permutations of Lacunary Intervals
• scientific article; zbMATH DE number 4055619
• Catalan numbers and pattern restricted set partitions
• Juxtaposing Catalan permutation classes with monotone ones

Cites work

• A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths
• A survey of stack-sorting disciplines
• Chain lengths in the Tamari lattice
• Combinatorics of permutations
• Counting 3-stack-sortable permutations
• Enumerating, Ranking and Unranking Binary Trees
• Enumeration of chains and saturated chains in Dyck lattices.
• Enumeration of edges in some lattices of paths
• Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Free probability theory and non-crossing partitions
• Generating functions for generating trees
• Generating trees and forbidden subsequences
• Generating trees and the Catalan and Schröder numbers
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 3178652 (Why is no real title available?)
• scientific article; zbMATH DE number 3995692 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Intervals in Catalan lattices and realizers of triangulations
• Lattice paths and pattern-avoiding uniquely sorted permutations
• Lattices of paths: representation theory and valutions
• Noncrossing partitions
• Noncrossing Partitions in Surprising Locations
• On a subposet of the Tamari lattice
• On maximal chains in the non-crossing partition lattice
• On Tamari lattices
• On the number of intervals in Tamari lattices
• Polyurethane toggles
• Poset structures on \((m+2)\)-angulations and polynomial bases of the quotient by \(G^{m}\)-quasisymmetric functions
• 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
• Realization of the Stasheff polytope
• Right-arm rotation distance between binary trees
• Sorted and/or sortable permutations
• Stack-sorting, set partitions, and Lassalle's sequence
• Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
• The number of Baxter permutations
• The number of intervals in the \(m\)-Tamari lattices
• Two integer sequences related to Catalan numbers

Cited in

(26)

• The permuted analogues of three Catalan sets
• From Motzkin to Catalan permutations
• Further bijections to pattern-avoiding valid hook configurations
• Stack-sorting with consecutive-pattern-avoiding stacks
• Troupes, cumulants, and stack-sorting
• Polyurethane toggles
• Uniquely sorted permutations
• Fertility monotonicity and average complexity of the stack-sorting map
• Counting 3-stack-sortable permutations
• Catalan recursion on externally ordered bases of unit interval positroids
• scientific article; zbMATH DE number 6670059 (Why is no real title available?)
• Stack-sorting for words
• scientific article; zbMATH DE number 6928921 (Why is no real title available?)
• Stack-sorting for Coxeter groups
• 312-Avoiding reduced valid hook configurations and duck words
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Lattice paths and pattern-avoiding uniquely sorted permutations
• Highly sorted permutations and Bell numbers
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Unimodality of a refinement of Lassalle's sequence
• Fertilitopes
• Dynamical aspects of \(\sigma\)-machines
• Enumeration of the Motzkin paths above a line of rational slope
• \(2 \times 2\) minors of recursive matrices related to generalized Dyck paths
• Periodic points of consecutive-pattern-avoiding stack-sorting maps
• Stack-sorting, set partitions, and Lassalle's sequence

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Catalan intervals and uniquely sorted permutations

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