A permutation \(\pi \in \mathbb {S}_n\) is k-balanced if every permutation of order k occurs in \(\pi \) equally often, through order-isomorphism. In this paper, we explicitly construct k-balanced permutations for \(k \le 3\) , and every n that satisfies the necessary divisibility conditions. In contrast, we prove that for \(k \ge 4\) , no such permutations exist. In fact, we show that in the case \(k \ge 4\) , every n-element permutation is at least \(\Omega _n(n^{k-1})\) far from being k-balanced. This lower bound is matched for \(k=4\) , by a construction based on the Erdős–Szekeres permutation.
