Enumerative recurrence conjecture for generalized stack-sortable permutations

For positive integers tt and nn, let Sortt,n(123,132)\operatorname{Sort}_{t,n}(123,132) be the set of length-nn permutations that are tt-stack-sortable under s123,132s_{123,132}. Enumerative recurrence conjecture. For any positive integer tt and n2t+1n\geq2t+1,

  • if nn is odd, then
Sortt,n(123,132)=n+32Sortt,n2(123,132);\lvert\operatorname{Sort}_{t,n}(123,132)\rvert=\frac{n+3}{2}\lvert\operatorname{Sort}_{t,n-2}(123,132)\rvert;
  • if nn is even, then
Sortt,n(123,132)=n+42Sortt,n2(123,132).\lvert\operatorname{Sort}_{t,n}(123,132)\rvert=\frac{n+4}{2}\lvert\operatorname{Sort}_{t,n-2}(123,132)\rvert.

This predicts an explicit length recurrence for the enumerator of tt-stack-sortable permutations under the specified generalized stack-sorting map; the source provides no resolution status.

Sources & referencesView supporting material

Primary source

Owen Zhang, “The Order of the (123, 132)-Avoiding Stack Sort”, arXiv:2405.01854 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.