Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.10779 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910132513800192 |
|---|---|
| author | Zhang, Jerry |
| author_facet | Zhang, Jerry |
| contents | We study the behavior of West's stack-sorting map $s$ on permutations whose last entry is also their least. Let $S_{n}':=\{\pi0\mid π\in S_n\}$ where $\pi0$ denotes the concatenation of $π$ and $0$. For each permutation $π\in S_n'$, we introduce a new combinatorial object known as the stack-sorting tableau $T_π$, which ultimately serves as the key ingredient in the first polynomial time algorithm for counting the number of $t$-stack-sortable permutations in $S_n'$. We then establish a precise relationship between the behavior of $s$ on $S_{n}'$ and on $S_{n}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_10779 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Polynomial Time Enumeration of t-Stack-Sortable Permutations Ending in Their Least Entry Zhang, Jerry Combinatorics 05A05 We study the behavior of West's stack-sorting map $s$ on permutations whose last entry is also their least. Let $S_{n}':=\{\pi0\mid π\in S_n\}$ where $\pi0$ denotes the concatenation of $π$ and $0$. For each permutation $π\in S_n'$, we introduce a new combinatorial object known as the stack-sorting tableau $T_π$, which ultimately serves as the key ingredient in the first polynomial time algorithm for counting the number of $t$-stack-sortable permutations in $S_n'$. We then establish a precise relationship between the behavior of $s$ on $S_{n}'$ and on $S_{n}$. |
| title | Polynomial Time Enumeration of t-Stack-Sortable Permutations Ending in Their Least Entry |
| topic | Combinatorics 05A05 |
| url | https://arxiv.org/abs/2604.10779 |