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.