2
$\begingroup$

In "Mathematics for the analysis of algorithms", I find the following problem.

How many permutations on $\{1 \dots n\}$ can be sorted by at most two bubble sort passes?

The book later goes on to say that it is $3^{n-2}\cdot 2$ which is the number of inversion tables $b_1 \dots b_n$ with all $b_j \leq 2$. I don't see how that works, as $4123$ is sorted in one pass and has $b_1 = 3$. Am I missing something?

I then tried to come up with a solution of my own by constructing and counting all such permutations. Say $B_k(n)$ is the number of permutations of $1 \dots n$, sorted in $k$ passes.

I found $B_1(n) = \sum \limits^{n-1}_{i=0} \binom{n-1}{i} = 2^{n-1}$ by assumption that every such permutation can be built by slicing $123\dots n$ into some chunks and moving the last number of each chunk to its front.

By a similar assumption it seems to me that $B_2(n) = \sum \limits ^n _{i=1} ~\sum \limits _{k_1 + k_2 + \cdots + k_i = n} ~\sum \limits^i _{j=1} B_1(k_j-1)$ with $k_j > 0$ and $B_1(0) = 1$. In words this is to slice $123 \dots n$ into $i$ chunks of size $k_i$ each and to move the largest number of each chunk as before, then to count $B_1$ of the length of the rest of the chunk.

I find myself unable to attack the above formula. If you could explain the answer my book gives, that would be lovely too.

  • 0
    You might be interested in [this article](http://arxiv.org/pdf/1008.5299v2.pdf). The last sentence gives (with a typo) the general formula that there are $(k+1)^{n-k}k!$ permutations of length $n\geqslant k$ sorted by $k$ bubble sort passes.2012-10-26

1 Answers 1

1

In each pass, an element can only be swapped once with an element greater than itself, since after that the pass moves on with the larger element and leaves the lesser one behind. Thus, a permutation cannot be swapped in two passes if there is an element that participates in more than two inversions as the lesser element. Conversely, if all elements are to the right of at most two greater elements, each pass is bound to sweep one of these past them, so the permutation can be sorted in two passes.

To find the number of permutations with each element participating in at most two inversions as the lesser element, place the elements in increasing order and note that for all elements up to $n-2$ you have three choices, then for $n-1$ you have two and for $n$ only one, yielding $2\cdot3^{n-2}$.

  • 0
    This definition is from another book. Mine doesn't bother with definitions :). Regardless, I do understand now, thanks. I won't accept this for a few days though, as I'd like to hear about my own construction of $B_2$.2012-10-25