Stack-sorting, set partitions, and Lassalle's sequence

DOI10.1016/J.JCTA.2020.105275MaRDI QIDQ778710zbMATH OpenOpenAlexFDO

Authors Colin Defant, Michael Engen, Jordan A. Miller

Publication date 3 July 2020

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

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

zbMATH Keywords

cumulantTutte polynomialset partitionstack-sortingLassalle's sequenceuniquely sorted permutationvalid hook configuration

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Graph polynomials (05C31) Partitions of sets (05A18)

Abstract: We exhibit a bijection between recently-introduced combinatorial objects known as valid hook configurations and certain weighted set partitions. When restricting our attention to set partitions that are matchings, we obtain three new combinatorial interpretations of Lassalle's sequence. One of these interpretations involves permutations that have exactly one preimage under the (West) stack-sorting map. We prove that the sequences obtained by counting these permutations according to their first entries are symmetric, and we conjecture that they are log-concave. We also obtain new recurrence relations involving Lassalle's sequence and the sequence that enumerates valid hook configurations. We end with several suggestions for future work.

Recommendations

• Stack-sorting preimages of permutation classes
• Further bijections to pattern-avoiding valid hook configurations
• Lattice paths and \((n - 2)\)-stack sortable permutations
• Uniquely sorted permutations
• Counting 3-stack-sortable permutations

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• A probabilistic interpretation of a sequence related to Narayana polynomials
• 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
• Combinatorics of permutations
• Counting 3-stack-sortable permutations
• Cumulants of the \(q\)-semicircular law, Tutte polynomials, and heaps
• Further bijections to pattern-avoiding valid hook configurations
• Lattice paths and pattern-avoiding uniquely sorted permutations
• Lectures on the Combinatorics of Free Probability
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• Postorder Preimages
• Preimages under the stack-sorting algorithm
• Proofs of some conjectures on monotonicity of number-theoretic and combinatorial sequences
• Sorted and/or sortable permutations
• Stack-sorting for words
• Statistics on lattice walks and \(q\)-Lassalle numbers
• Two integer sequences related to Catalan numbers
• Unimodality, log-concavity, real-rootedness and beyond
• Wilf-equivalence for singleton classes
• Zeta Functions and the Log Behaviour of Combinatorial Sequences

Cited in

(33)

• Preimages under the bubblesort operator
• Troupes, cumulants, and stack-sorting
• Catalan intervals and uniquely sorted permutations
• Fertility monotonicity and average complexity of the stack-sorting map
• Counting 3-stack-sortable permutations
• Sorting with a popqueue
• Highly sorted permutations and Bell numbers
• A lift of West's stack-sorting map to partition diagrams
• Stack-sorting for Coxeter groups
• Polyurethane toggles
• Characterization and enumeration of preimages under the \texttt{Queuesort} algorithm
• Stack sorting with increasing and decreasing stacks
• Troupes, cumulants, and stack-sorting
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• The combinatorics of a tree-like functional equation for connected chord diagrams
• Lattice paths and \((n - 2)\)-stack sortable permutations
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• scientific article; zbMATH DE number 1741785 (Why is no real title available?)
• A survey of stack-sorting disciplines
• Dynamical aspects of \(\sigma\)-machines
• scientific article; zbMATH DE number 1780162 (Why is no real title available?)
• Stack-sorting with consecutive-pattern-avoiding stacks
• 312-Avoiding reduced valid hook configurations and duck words
• On a pattern sequencing problem to minimize the maximum number of open stacks
• Stack-sorting preimages of permutation classes
• Fertilitopes
• Uniquely sorted permutations
• Stack-sorting for words
• Preimages under the Queuesort algorithm
• Restricted stacks as functions
• Further bijections to pattern-avoiding valid hook configurations
• Lattice paths and pattern-avoiding uniquely sorted permutations
• Unimodality of a refinement of Lassalle's sequence

This page was built for publication: Stack-sorting, set partitions, and Lassalle's sequence

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