What is the probability of single round bubble sort getting the right order

Question

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).

Answer 1

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

Answer 2

Following up on the answer given by @Empy2, there are $n!$ possible permutations of n numbers. We want only permutations that end up in a sorted array after a single pass. A single pass runs $n-1$ operations that could be encoded as 0 (no swap) or 1 (swap). In total there are $2^{n-1}$ possible swap ombinations for the last pass of the buble sort. So to get the probability you just divide it by the total number of permutations: $$ p=\frac {2^{n-1}} {n!} $$ In case of 5 item list it's $2^4/5!=0.1(3)$