Skip to content
DraconiticResearch
Search Sources API
194,220 studies31 sourcesUpdated 51 min ago
PreprintCC BY 4.0arXiv

Motzkin Numbers Count 2-Stack-Sortable Permutations Ending in Their Least Entry

  • Ryota Inagaki
  • Michael Luo
Open at sourcePDFDOICite

Abstract

We prove the following conjecture of Zhang (arXiv:2604.10779, Conjecture 6.1): for n ≥ 0, the number of $2$-stack-sortable permutations of {0,1,…,n} ending in $0$ is the nth Motzkin number. By Zhang's result, there is a bijection between $2$-stack-sortable permutations ending in their least element and standard composition tableaux of width at most $2$. We then show bijectively that there are an equal number of these and standard Young tableaux of width at most $3$, which are known to be counted by the Motzkin numbers.

Related

  1. A Short Proof of Zhang's Conjecture on Stack-Sortable Permutations
    Maximus Lu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. On a conjecture concerning two-stack sortable permutations
    Yongzhou Wen, Sherry H. F. Yan
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Motzkin paths, 321-avoiding permutations, and standard Young tableaux with rows of equal parity
    Ryan J. Amaral, Juan B. Gil, Michael D. Weiner
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Ending currents of hyperbolic group actions
    Yair Minsky, Tianqi Wang
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  5. The Cuntz-Pimsner algebra of the simplest Motzkin subproduct system is 2-subhomogeneous
    Valeriano Aiello, Arnaud Brothier
    arXivPreprintarXiv licenceFull textAlgebra & number theoryAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{inagaki2026motzkin,
  title = {{Motzkin Numbers Count 2-Stack-Sortable Permutations Ending in Their Least Entry}},
  author = {Ryota Inagaki and Michael Luo},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.02756},
  eprint = {2610.02756},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.02756},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Motzkin Numbers Count 2-Stack-Sortable Permutations Ending in Their Least Entry
AU  - Ryota Inagaki
AU  - Michael Luo
PY  - 2026
DA  - 2026/10/02
PB  - arXiv
DO  - 10.48550/arxiv.2610.02756
UR  - https://arxiv.org/abs/2610.02756
AB  - We prove the following conjecture of Zhang (arXiv:2604.10779, Conjecture 6.1): for n ≥ 0, the number of $2$-stack-sortable permutations of {0,1,…,n} ending in $0$ is the nth Motzkin number. By Zhang's result, there is a bijection between $2$-stack-sortable permutations ending in their least element and standard composition tableaux of width at most $2$. We then show bijectively that there are an equal number of these and standard Young tableaux of width at most $3$, which are known to be counted by the Motzkin numbers.
ER  -