I am working on a problem where you're given n distinct numbers, and you want to find the number of permutations such that it takes bubble sort at most 1 pass to complete.
e.g., if n=3, then the following permutations would only require 1 pass
1 2 3
1 3 2
3 1 2
2 1 3
But
3 2 1
2 3 1
would require more than 1 pass. Apparently the answer is 2^{n - 1}, but I am not sure how to prove this for the general n case.
My question is, what are the general constraints for a sequence to allow for it to be sorted with 1 pass of bubble sort?
It is difficult for me to come up with a generic formula to generate the permutations for larger n.