What is the probability of single round bubble sort getting the right order
Given a permutation of {1,2,...,n}, what is the probability of a single round bubble sort getting the right order?
For example:
a). 5,1,2,3,4 -> 1,5,2,3,4 -> 1,2,5,3,4 -> 1,2,3,5,4 -> 1,2,3,4,5. After the first round, the order is right;
b). 1,2,5,4,3 -> 1,2,4,5,3 -> 1,2,4,3,5, After the first round, the order is still not right.
I guess the equivalent condition is that a least n-1 numbers are in the right order.
If it is right, how to calculated the probability?
If we fix the four elements with right and put the left one anywhere, there will be a lot of duplicates. e.g.
fix 1,2,3,4 and put 5: 1,2,3,(5),4 is duplicate with fix 1,2,3,5 and put 4: 1,2,3,5,(4).
There are $n-1$ comparisons, so $2^{n-1}$ possible sequences of actions - swap or don't swap. To find the permutations, start with 1,2,3,4,5 and undo a sequence.
For example, if $n=5$, there are $2^4=16$ out of $5!=120$ that end after one round of bubble sort.
For one of them, you do Swap,Leave,Swap,Swap. That is
A: Swap places 1,2;
B: Leave places 2,3;
C: Swap places 3,4;
D: Swap places 4,5, end with 1,2,3,4,5.
To find out the starting point for that one, undo the sequence
D: UnSwap places 4,5, end with 1,2,3,5,4
C: Unswap places 3,4, end with 1,2,5,3,4
B Leave 2,3 alone
A: Unswap places 1,2, end with 2,1,5,3,4