Deck of 5 cards Shuffling Problem but only allowed to choose two adjacent cards

Question

Say I have a deck of 5 cards that are labeled 1, 2, 3, 4, 5. 1 being at the top and 5 being at the bottom. The rules of this game are as follows. You can take only take two adjacent cards (1 2, 2 3, 3 4, or 4 5) and insert them anywhere else in the stack. For example I could take the 1 2 out and put it in between 4 and 5 to make the deck look like 3 4 1 2 5. I cannot change the order of the two adjacent cards I take out and reinsert. With the deck 3 4 1 2 5, I can take for example, the 2 5 and move it to the front to make 2 5 3 4 1.

The question is as follows:

I use the above rule starting with the deck 1 2 3 4 5. If I use this "shuffle" maneuver as many times as I would like, is it possible to get to the deck 2 1 3 4 5. I ran a computer program and it said this isn't possible. In fact I noticed that there were 60 decks possible starting with 1 2 3 4 5. I can't seem prove this without blindly listing all decks.

Is there a way to prove that 1 2 3 4 5 cant get to 2 1 3 4 5?

Answer 1

Let's observe that the initial permutation has 0 inevrsions, therefore it's even.
When moving $ a, b $, we can handle the folowing situations:

1. Bypassing a number $ d \leq a, b $: This adds 2 inversions, if we are moving the group „to the right”, otherwise, this substracts 2 inversions.
2. Bypassing a number $ d \geq a, b $: This adds 2 inversions, if we are moving the group „to the left”, otherwise, this substracts 2 inversions.
3. Bypassing a number $ d \leq a $ $ d \geq b $: This adds no inversions, as we will create a new inversion with one of the $ a, b$ and we will remove one with the other.
4. Bypassing a number $ d \geq a $ $ d \leq b $: This adds no inversions, as we will create a new inversion with one of the $ a, b$ and we will remove one with the other.

This creates the parity of the permutation even and an invariant property.

For the given permutation 2 1 3 4 5, the parity is odd, as we have only one inversion: $ (2, 1) $.