How Balanced Can Permutations Be?

Abstract

A permutation $\ddot{I}€\in {\mathbb{S}}_n$ is $k$-balanced if every permutation of order $k$ occurs in $\ddot{I}€$ 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 $\hat{I}{\text{c◯}}_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.