Counting 3-stack-sortable permutations

DOI10.1016/J.JCTA.2020.105209zbMATH Open1433.05005arXiv1903.09138OpenAlexW3001233149WikidataQ126315343 ScholiaQ126315343MaRDI QIDQ2299650FDOQ2299650

Authors: Colin Defant 

Publication date: 21 February 2020

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

Abstract: We prove a "decomposition lemma" that allows us to count preimages of certain sets of permutations under West's stack-sorting map $s$. As a first application, we give a new proof of Zeilberger's formula for the number of 2-stack-sortable permutations in $S_n$. Our proof generalizes, allowing us to find an algebraic equation satisfied by the generating function that counts 2-stack-sortable permutations according to length, number of descents, and number of peaks. The same method yields a recurrence relation for $W_3(n)$, the number of 3-stack-sortable permutations in $S_n$. We compute $W_3(n)$ for $nle174$, extending the 13 terms of this sequence that were known before. We also prove the first nontrivial lower bound for $limlimit{s}_{noinfty}{W}_3(n{)}^{1/n}$. Invoking a result of Kremer, we also prove that $limlimit{s}_{noinfty}{W}_t(n{)}^{1/n}geq(sqrtt+1{)}^2$ for all $tgeq1$, which we use to improve a result of Smith. Our computations allow us to disprove a conjecture of B'ona, although we do not yet know for sure which one. We can refine our methods to obtain a recurrence for the number of 3-stack-sortable permutations in $S_n$ with $k$ descents and $p$ peaks. This produces a large amount of evidence supporting a real-rootedness conjecture of B'ona. Using part of the theory of valid hook configurations, we give a new proof of a $gamma$-nonnegativity result of Br"and'en, which in turn implies an older result of B'ona. We then answer a question of the current author by producing a set $Asubseteq{S}_{11}$ such that $su{m}_{sigmain{s}^{-1}(A)}{x}^{extdes(sigma)}$ has nonreal roots. We interpret this as partial evidence against the same real-rootedness conjecture of B'ona that we found evidence supporting. Examining the parities of the numbers $W_3(n)$, we obtain strong evidence against yet another conjecture of B'ona. We end with some conjectures of our own.

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

Recommendations

• Asymptotics of 3-stack-sortable permutations
• Stack words and a bound for 3-stack sortable permutations
• Counting \(\mathbf {(3+1)}\)-avoiding permutations
• Stack-sortable permutations and beyond
• Highly sorted permutations with respect to a 312-avoiding stack
• Counting Stirling permutations by number of pushes
• Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three
• Counting Pop-Stacked Permutations in Polynomial Time
• A survey of stack sortable permutations
• scientific article; zbMATH DE number 7106992

zbMATH Keywords

descentpolynomial-time algorithmpermutation patternpeak\(\gamma\)-nonnegativitystack-sortingvalid hook configurationreal-rooted

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On linear transformations preserving the Pólya frequency property
• Combinatorics of permutations
• Unimodality, log-concavity, real-rootedness and beyond
• Actions on permutations and unimodality of descent polynomials
• Polynomial equations with one catalytic variable, algebraic series and map enumeration
• A survey of stack-sorting disciplines
• Refined enumeration of permutations sorted with two stacks and a \(D_8\)-symmetry
• Describing West-3-stack-sortable permutations with permutation patterns
• Postscript: ``Permutations with forbidden subsequences and a generalized Schröder number [Discrete Mathematics 218 (2000) 121--130]
• Permutations with forbidden subsequences and a generalized Schröder number
• 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
• A combinatorial proof of J. West's conjecture
• Sorted and/or sortable permutations
• Symmetry and unimodality in \(t\)-stack sortable permutations
• Permutations with forbidden subsequences and nonseparable planar maps
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
• Descents in \(t\)-sorted permutations
• Sorting and preimages of pattern classes
• Permutations sortable by \(n - 4\) passes through a stack
• Stack-sorting preimages of permutation classes
• A simplicial complex of 2-stack sortable permutations
• What is an Answer?
• Further bijections to pattern-avoiding valid hook configurations
• Catalan intervals and uniquely sorted permutations
• Two first-order logics of permutations
• Preimages under the stack-sorting algorithm
• Postorder Preimages
• Stack-sorting for Words
• Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations
• Stack words and a bound for 3-stack sortable permutations
• Stack-sorting, set partitions, and Lassalle's sequence
• Comparing algorithms for sorting with \(t\) stacks in series
• Fighting fish
• Staircases, dominoes, and the growth rate of 1324-avoiders
• Fighting fish and two-stack sortable permutations
• Fertility numbers
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Polyurethane toggles
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma

Cited In (36)

• Fertility monotonicity and average complexity of the stack-sorting map
• Describing West-3-stack-sortable permutations with permutation patterns
• Preimages under the stack-sorting algorithm
• Highly sorted permutations and Bell numbers
• Quantifying noninvertibility in discrete dynamical systems
• On the real-rootedness of the descent polynomials of \((n-2)\)-stack sortable permutations
• Stack-sorting for Words
• 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)\)!)
• Pop-stack-sorting for Coxeter groups
• Stack-sorting for Coxeter groups
• Polyurethane toggles
• Stacking Blocks and Counting Permutations
• Stack sorting with increasing and decreasing stacks
• Permutations with forbidden subsequences and nonseparable planar maps
• Asymptotics of 3-stack-sortable permutations
• Highly sorted permutations with respect to a 312-avoiding stack
• Troupes, cumulants, and stack-sorting
• Sorting Cayley permutations with pattern-avoiding machines
• Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Stack-sortable permutations and beyond
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Lattice paths and \((n - 2)\)-stack sortable permutations
• Stack words and a bound for 3-stack sortable permutations
• Stack-sorting, set partitions, and Lassalle's sequence
• Meeting covered elements in \(\nu\)-Tamari lattices
• Deterministic stack-sorting for set partitions
• Asymptotic normality in t-stack sortable permutations
• Stack-sorting with consecutive-pattern-avoiding stacks
• Dynamics of pop-tsack torsing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fertilitopes
• Uniquely sorted permutations
• Troupes, cumulants, and stack-sorting
• Catalan intervals and uniquely sorted permutations

Uses Software

• OEIS

This page was built for publication: Counting 3-stack-sortable permutations

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