Motzkin Numbers Count 2-Stack-Sortable Permutations Ending in Their Least Entry
We prove the following conjecture of Zhang (arXiv:2604.10779, Conjecture 6.1): for $n \geq 0$, the number of $2$-stack-sortable permutations of $\{0,1,\dots,n\}$ ending in $0$ is the $n$th 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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.02756
curl -X POST /api/v1/records/arxiv/2610.02756/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.02756/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'