Abstract
A permutation $$\pi \in \mathbb {S}_n$$ π ∈ 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$$ k ≤ 3 , and every n that satisfies the necessary divisibility conditions. In contrast, we prove that for $$k \ge 4$$ k ≥ 4 , no such permutations exist. In fact, we show that in the case $$k \ge 4$$ k ≥ 4 , every n-element permutation is at least $$\Omega _n(n^{k-1})$$ Ω n ( n k - 1 ) far from being k-balanced. This lower bound is matched for $$k=4$$ k = 4 , by a construction based on the Erdős–Szekeres permutation.
Funding Information
  • Hebrew University of Jerusalem

This publication has 16 references indexed in Scilit: