Shape-Wilf-ordering on permutations of length 3 (Q1010613)

Summary: The research on pattern-avoidance has yielded so far limited knowledge on Wilf-ordering of permutations. The Stanley-Wilf limits \(\lim_{n\rightarrow \infty} \root n \of{|S_n(\tau)|}\) and further works suggest asymptotic ordering of layered versus monotone patterns. Yet, \textit{M. Bóna} [''The solution of a conjecture of Wilf and Stanley for all layered patterns,'' J. Comb. Theory, Ser. A 85, No.\,1, 96--104 (1999; Zbl 0919.05002)] has provided essentially the only known up to now result of its type on complete ordering of \(S_k\) for \(k=4: |S_n(1342)|<|S_n(1234)|<|S_n(1324)|\) for \(n\geq 7\), along with some other sporadic examples in Wilf-ordering. We give a different proof of this result by ordering \(S_3\) up to the stronger shape-Wilf-order: \(|S_Y(213)|\leq |S_Y(123)|\leq |S_Y(312)|\) for any Young diagram \(Y\), derive as a consequence that \(|S_Y(k+2,k+1,k+3,\tau)|\leq |S_Y(k+1,k+2,k+3,\tau)|\leq |S_Y(k+3,k+1,k+2,\tau)|\) for any \(\tau\in S_k\), and find out when equalities are obtained. (In particular, for specific \(Y\)'s we find out that \(|S_Y(123)|=|S_Y(312)|\) coincide with every other Fibonacci term.) This strengthens and generalizes Bóna's result to arbitrary length permutations. While all length-3 permutations have been shown in numerous ways to be Wilf-equivalent, the current paper distinguishes between and orders these permutations by employing all Young diagrams. This opens up the question of whether shape-Wilf-ordering of permutations, or some generalization of it, is not the ``true'' way of approaching pattern-avoidance ordering.