# Bubble sort in two passes

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.

-
You need to explain what you mean by $b_j$, $d_i$, $k_j$, and so forth. Otherwise your question is not understandable. – Henning Makholm Oct 25 '12 at 16:00
$b_k$ is properly introduced. $d_k$ appears to be used in the same way as in Wikipedia, but if so, there's a typo in the question and the first $b_j$ should be $d_j$? Also, if so, then $4123$ has $d_1=1$, since $1$ is the smaller element in one inversion, namely $41$, so everything seems to be OK there. You seem to be counting inversions involving $4$ as the larger element, but they don't matter. – joriki Oct 25 '12 at 16:05
I infer from your edit that you're not using the same notation as the Wikipedia article after all. In that case you should indeed explain the notation. – joriki Oct 25 '12 at 16:08
Sorry about the confusion. The book uses $b_k$ for the elements of the inversion table. – Karolis Juodelė Oct 25 '12 at 16:15
You might be interested in this article. 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. – David Bevan Oct 26 '12 at 9:13

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}$.
What is an inversion table? I found that the table of $x_1x_2 \dots x_n$ is $d_1 d_2 \dots d_n$ with $d_i = |\{x_j : i<j, x_i > x_j\}|$. This seems backwards from the way you are using it. – Karolis Juodelė Oct 25 '12 at 16:24
@Karolis: I thought your book uses $b_k$? Anyway, I think if you understand the answer you should be able to apply it with whatever definition of an inversion table you find. – joriki Oct 25 '12 at 16:32
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$. – Karolis Juodelė Oct 25 '12 at 16:47