← All problems

Zhang’s conjecture on stack-sortable permutations

For every integer n≥0n\ge 0, let An+1\mathcal{A}_{n+1} be the set of 22-stack-sortable permutations π∈Sn+1\pi\in S_{n+1} satisfying πn+1=1\pi_{n+1}=1. Zhang's conjecture asserts that ∣An+1∣=Mn\lvert\mathcal{A}_{n+1}\rvert=M_n, where MnM_n is the nnth Motzkin number, defined by M0=1M_0=1 and Mn=Mn−1+∑i=0n−2MiMn−2−iM_n=M_{n-1}+\sum_{i=0}^{n-2}M_iM_{n-2-i} for n≥1n\ge 1.

References

Progress summary

Refreshed
Open · solution reported

An October 2026 preprint claims to prove the conjecture, but the result has not been independently checked.

Zhang’s conjecture asserts that the relevant 22-stack-sortable permutations of size n+1n+1 are counted by the nnth Motzkin number. Zhang formulated this as Conjecture 6.1 in work on stack-sorting tableaux.

Known results

  • Knuth established the Catalan enumeration for 11-stack-sortable permutations.
  • Zeilberger proved an explicit formula for the ordinary 22-stack-sortable count.
  • Zhang gave an O(n3t+1)O(n^{3t+1}) algorithm for the least-entry-ending count for fixed tt.

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 22, then bijected with standard Young tableaux of width at most 33, 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.

Sources

Solutions 0

No solutions have been posted yet.