Skip to main content
edited tags; edited tags
Link
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171
Source Link

Swaps in a permutation across an index

We are given two positive integers $N$ and $K$ such that $K < N$. We start with an array $A=[1,2,\dots,N]$. We can choose an arbitrary index $i \in \{1,2,\dots,N-1\}$ and we can swap $A[i]$ with $A[i+1]$ provided that $A[i] < A[i+1]$. We do such swaps until no more such swaps are possible. (This happens when the array $A$ is completely reversed, i.e., $A=[N, N-1, \dots, 1]$ after exactly $N(N-1)/2$ swaps, since every swap increases the number of inversions by $1$.) Let $S_{N,K}$ be the maximum possible number of swaps of $A[K]$ and $A[K+1]$ that can happen (taken over all possible legal sequences of swaps).

What are the best known lower and upper bounds for $S^*_N = \max\{S_{N,1}, S_{N,2}, \dots, S_{N,N-1}\}$ in terms of $N$?

Note: The trivial bounds $N-1 = S_{N,1} \le S^*_N \le N(N-1)/2$ are too loose for my taste. I would like to have lower and upper bounds that are within a constant factor of each other.