错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On a Conjecture on Pattern-Avoiding Machines

  • Christopher Bao,
  • Giulio Cerbai,
  • Yunseo Choi,
  • Katelyn Gan,
  • Owen Zhang

摘要

Let s be West’s stack-sorting map, and let \(s_{T}\) s T be the generalized stack-sorting map, where instead of being required to increase, the stack avoids subpermutations that are order-isomorphic to any permutation in the set T. In 2020, Cerbai, Claesson, and Ferrari introduced the \(\sigma \) σ -machine \(s \circ s_{\sigma }\) s s σ as a generalization of West’s 2-stack-sorting-map \(s \circ s\) s s . As a further generalization, in 2021, Baril, Cerbai, Khalil, and Vajnovski introduced the \((\sigma , \tau )\) ( σ , τ ) -machine \(s \circ s_{\sigma , \tau }\) s s σ , τ and enumerated \(\textrm{Sort}_{n}(\sigma ,\tau )\) Sort n ( σ , τ ) —the number of permutations in \(S_n\) S n that are mapped to the identity by the \((\sigma , \tau )\) ( σ , τ ) -machine—for six pairs of length 3 permutations \((\sigma , \tau )\) ( σ , τ ) . In this work, we settle a conjecture by Baril, Cerbai, Khalil, and Vajnovski on the only remaining pair of length 3 patterns \((\sigma , \tau ) = (132, 321)\) ( σ , τ ) = ( 132 , 321 ) for which \(|\textrm{Sort}_{n}(\sigma , \tau )|\) | Sort n ( σ , τ ) | appears in the OEIS. In addition, we enumerate \(\textrm{Sort}_n(123, 321)\) Sort n ( 123 , 321 ) , which does not appear in the OEIS, but has a simple closed form.