How balanced can permutations be? (Q6999747)

This paper introduces and analyzes the notion of \(k\)-balanced permutations within the symmetric group \(S_{n}\), framed through the lens of pattern containment via order-isomorphism. For a given \(\pi\in S_{n}\), and a subset \(S=\{s_{1},\dots,s_{k}\}\subseteq\{1,\dots,n\}\), the permutation \(\pi\) is said to be order-isomorphic to \(\tau\in S_{k}\) on \(S\) if \(\pi(s_{i})<\pi(s_{j})\) if and only if \(\tau(i)<\tau(j)\) for all \(i,j\in\{1,2,\dots,k\}\). The quantity \(\#\tau(\pi)\) counts the number of such subsets \(S\) for which \(\pi(S)\cong\tau\). A permutation \(\pi\) is defined to be \(k\)-balanced if \(\#\tau(\pi)=\binom{n}{k}/k!\) for all \(\tau\in S_{k}\).\par The authors prove that \(k\)-balancedness implies \(r\)-balancedness for all \(r<k\), and classify the values of \(n\) admitting \(2\)-balanced permutations: precisely those for which \(n\equiv0\) or \(1\pmod 4\). For \(k=3\), they derive a partial characterization using rotation-invariant permutations, showing that \(3\)-balanced permutations exist for \(n\geq9\) if and only if \(n\equiv0\), \(1\), \(9\), \(20\), \(28\), or \(29\pmod{36}\). Explicit constructions and group-theoretic analysis support this result. In contrast, they establish that no \(4\)-balanced permutation exists for any \(n\).\par Using \(k\)-profiles, the authors analyze the extent to which a permutation deviates from being \(k\)-balanced for \(k>4\).