Enumerative recurrence conjecture for generalized stack-sortable permutations

About 2 years old · traced to

For positive integers tt and nn, let Sort⁡t,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 n≥2t+1n\geq2t+1,

  • if nn is odd, then
∣Sort⁡t,n(123,132)∣=n+32∣Sort⁡t,n−2(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
∣Sort⁡t,n(123,132)∣=n+42∣Sort⁡t,n−2(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.

References

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.