Zhang’s conjecture on stack-sortable permutations
For every integer , let be the set of -stack-sortable permutations satisfying . Zhang's conjecture asserts that , where is the th Motzkin number, defined by and for .
References
- A Short Proof of Zhang's Conjecture on Stack-Sortable Permutations — arXiv — Maximus Lu
Source: arXiv
Progress summary
An October 2026 preprint claims to prove the conjecture, but the result has not been independently checked.
Zhang’s conjecture asserts that the relevant -stack-sortable permutations of size are counted by the th Motzkin number. Zhang formulated this as Conjecture 6.1 in work on stack-sorting tableaux.
Known results
- Knuth established the Catalan enumeration for -stack-sortable permutations.
- Zeilberger proved an explicit formula for the ordinary -stack-sortable count.
- Zhang gave an algorithm for the least-entry-ending count for fixed .
October 2026 claimed proof
A preprint by Maximus Lu claims a short proof: the relevant permutations are identified with standard composition tableaux of width at most , then bijected with standard Young tableaux of width at most , whose enumeration is the Motzkin sequence. A separate retrieved arXiv preprint reports the same theorem, but no independent mathematical assessment was found.
Current status (as of October 2026): Zhang’s conjecture has a claimed preprint proof, but its correctness remains unverified.
Solutions 0
No solutions have been posted yet.