I came up with the following algorithm on a whim, and it doesn't relate to any deeper mathematics, but I'd like to see if someone can prove a connection it has to a sequence I found. You can think of the algorithm as a way to solve a game. Say that you have $n$ elements in some deranged order, and you need to put them in the correct order. You don't know the correct order, but every time you transpose two elements, for each one, you get told if its new position is the correct one. This algorithm implements a brute force solution to such a game.
Let $D$ be a derangement (permutation with no fixed points) on $n$ elements, written in one line notation. The algorithm proceeds as follows:
- Identify the left-most element that is not a fixed point and label it $x$.
- Transpose $x$ with the left-most element $y$ such that $y$ is not a fixed point and at no point in the algorithm did $x$ occupy the space that $y$ occupies.
- Repeat step 2 until $x$ is a fixed point.
- Go back to step 1 and repeat until you get the identity permutation.
For example, say we start with $53421$. Here's the process the algorithm takes: $53421\to 35421\to 34521\to 34251\to 34215\to 24315\to 42315\to 12345$.
We label $5$ as $x$ and keep transposing it with the element to the right of it until it is the last element. We then label $3$ as $x$. However, we don't transpose $3$ with $4$ since $3$ has already been in the second place at some point in the algorithm, so we transpose it with $2$ instead. Then we label $2$ as $x$ and transpose it with $4$. Finally, we label $4$ as $x$ and transpose it with $1$, the only other non-fixed point, completing the algorithm.
What I'm interested in is the number of transpositions required for derangements- in particular, for derangements of length $n$, what is the largest number of transpositions required. The previous derangement, along with $54123$, are the derangements of length $5$ using the most transpositions, with the algorithm taking $7$ transpositions for each.
I've written code to produce, for each $n$, the "worst case" derangements and the number of transpositions they require. Here's some of the data:
\begin{array}{|c|c|c|} \hline n & \textrm{"Worst case" derangements} & \textrm{Number of transpositions} \\ 2 & 21 & 1 \\ 3 & 231, 312 & 2 \\ 4 & 4312 & 5 \\ 5 & 53421, 54123 & 7 \\ 6 & 654213 & 11 \\ 7 & 7645123, 7645231 & 15 \\ 8 & 87561342 & 21 \\ 9 & 985617324, 985617432, 985762413, 985763421, 986713425 & 25\\ 10 & 0968174235 & 32 \end{array}
Interestingly, the number of worst case derangements seems to alternate between $1$ and $2$ until we reach $n=9$. The other interesting result is that the worst case number of transpositions matches the sequence A084935 on OEIS. I don't see any obvious connections between that sequence and what I'm counting here, but they do agree on the first $10$ entries. Are these two sequences equal?