I'm assuming that a pass of bubble sort on the array $A[1],\ldots,A[n]$ proceeds as follows:
- If $A[1] > A[2]$ then swap $A[1]$ and $A[2]$.
- If $A[2] > A[3]$ then swap $A[2]$ and $A[3]$.
- ...
- If $A[n-1] > A[n]$ then swap $A[n-1]$ and $A[n]$.
Bubble sort halts after a pass in which no swaps were made.
As is evident, if bubble sort halts after one pass, then the array must have been sorted.
When does bubble sort halt after two passes? If after the first pass, the array is sorted. In this case, if we know which swaps were made, then we can recover the input permutation. Furthermore, different sets of swaps correspond to different initial permutations. It follows that there are $2^{n-1}-1$ permutations that cause bubble sort to halt after exactly two passes. Together with the identity permutation, it follows that there are $2^{n-1}$ permutations that cause bubble sort to halt within two passes.
How do these permutations look like? Suppose that the first $k$ swaps are made, and then the following swap isn't made. Since the first $k$ swaps are made but the following one isn't made, at the end of the pass the first $k+1$ elements of the array will be $A[2],\ldots,A[k+1],A[1]$, which must correspond to the permutation $1,\ldots,k+1$. Hence the original permutation started $k+1,1,\ldots,k$.
From here, it's not too difficult to describe all $2^{n-1}$ permutations. Starting with the identity permutation, partition it in an arbitrary way, and rotate each part one step to the right. For example, when $n = 3$ we get:
- $1|2|3 \to 1|2|3$.
- $1|23 \to 1|32$.
- $12|3 \to 21|3$.
- $123 \to 312$.
Each division in the partition corresponds to a step in the pass during which there was no swap.
Here is another way of describing these permutations: they avoid the patterns $231$ and $321$. This means that for any $i<j<k$, it cannot be that $A[k] < A[i],A[j]$. To prove this, we show that any permutation above satisfies this constraint, and then prove the converse.
Consider any of the $2^{n-1}$ permutations above, and let $i<j<k$. Since each element in a part is smaller than each element in a subsequent part, $A[k] < A[i]$ is only possible if $i,j,k$ are all in the same part. Moreover, $A[k] < A[j]$ for indices $j<k$ in the same part only if $j$ is the first element in the part, which is impossible since $j>i$.
Suppose now that we are given a $(231,321)$-avoiding permutation. Let $i$ be any index such that $A[i] > i$. All elements in $i,\ldots,A[i]-1$ must appear before all elements in $A[i]+1,\ldots,n$, since otherwise there will be a copy of $231$. Furthermore, the former must appear in increasing order, since otherwise there will be a copy of $321$. Therefore the part of the array that follows $A[i]$ is $A[i],i,i+1,\ldots,A[i]-1$.
Imagine now scanning the array in the order $A[1],A[2],\ldots$. The first time that $A[i] \neq i$, necessarily $A[i] > i$ (since we've already seen all smaller elements), and so the following elements are $i,\ldots,A[i]-1$. When we continue the scan, again the first time that $A[i] \neq i$ we must have $A[i] > i$ (since we've already seen all smaller elements), and so on. Therefore the array is of the form above.
