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

DOI10.1016/J.JCTA.2020.105275zbMATH Open1442.05006arXiv1809.01340OpenAlexW3030809477MaRDI QIDQ778710FDOQ778710

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)

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.

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

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

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)

Cites Work

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

Cited In (33)

• Sorting with a popqueue
• Fertility monotonicity and average complexity of the stack-sorting map
• Counting 3-stack-sortable permutations
• Highly sorted permutations and Bell numbers
• A lift of West's stack-sorting map to partition diagrams
• Stack-sorting for Coxeter groups
• Characterization and enumeration of preimages under the \texttt{Queuesort} algorithm
• Polyurethane toggles
• 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
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Lattice paths and \((n - 2)\)-stack sortable permutations
• Title not available (Why is that?)
• Dynamical aspects of \(\sigma\)-machines
• A survey of stack-sorting disciplines
• Title not available (Why is that?)
• 312-Avoiding reduced valid hook configurations and duck words
• Stack-sorting with consecutive-pattern-avoiding stacks
• On a pattern sequencing problem to minimize the maximum number of open stacks
• Stack-sorting preimages of permutation classes
• Fertilitopes
• Stack-sorting for words
• Uniquely sorted permutations
• Lattice paths and pattern-avoiding uniquely sorted permutations
• Unimodality of a refinement of Lassalle's sequence
• Further bijections to pattern-avoiding valid hook configurations
• Preimages under the Queuesort algorithm
• Restricted stacks as functions
• Preimages under the bubblesort operator
• Troupes, cumulants, and stack-sorting
• Catalan intervals and uniquely sorted permutations

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)