# Bubble sorting question

Consider that we use the bubble-sorting algorithm to sort a string of size $n$. We know then that the maximum number of swaps results when the string is in reverse order- this gives $\frac{n(n-1)}{2}$ swaps. There are a total of $n!$ strings. Can we generalize the number of strings that can be sorted in a minimum of any given number of swaps between 0 and $\frac{n(n-1)}{2}$ inclusive? Looking at small cases, I see that this list seems symmetric- for $n=3$, there is 1 string that can be sorted in 0 swaps, 2 strings that can be sorted in a minimum of 1 swaps, 2 that can be sorted in a minimum of 2 swaps, and 1 that can be sorted in a minimum of 3 swaps. So our list for $n=3$ is $1,2,2,1$. Perhaps if we create pyramid of the lists for all $n$ we might be able to find some patterns? The list for any $n$ should sum to $n!$.

Finding patterns/repetitions using the definition of $G$ given here might be productive, perhaps.

-
You might be interested in en.wikipedia.org/wiki/Pascal%27s_triangle – valtron Nov 26 '12 at 16:01
I was trying to notice the similarities, but do not think they are quite that evident. – Johann Linus Nov 26 '12 at 16:01
Looks like I posted without thinking. $n!$ is faster than the sum of the Pascal triangle's rows grow. Here's the recurrence I think you're looking for, though: take row $n$, make $n+1$ copies, and shift each copy right by $0$ though $n$. Sum the copies. This preserves the factorial sum. For $n=4$, this produces $1,3,5,6,5,3,1$. – valtron Nov 26 '12 at 16:15
@valtron Can that algorithm be made into an explicit formula or recursion? – Johann Linus Nov 26 '12 at 16:17
@valtron When I tried n=4 I got 6 strings with a minimum of 2 swaps... – Johann Linus Nov 26 '12 at 16:20

This can be computed using the fact that Bubblesort removes exactly one inversion per swap operation. So the number of swaps has the same distribution as the number of inversions, which has the ordinary generating function $$f(z) = \prod_{k=0}^{n-1} \sum_{m=0}^k z^m.$$ E.g. for $n=4$ we get $$f(z) = (1) \left( 1+z \right) \left( 1+z+{z}^{2} \right) \left( 1+z+{z}^{2}+{z}^{3} \right) = 1+3\,z+5\,{z}^{2}+6\,{z}^{3}+5\,{z}^{4}+3\,{z}^{5}+{z}^{6}.$$ The expected number of swaps is $$\frac{1}{n!} \left. \frac{d}{dz} f(z)\right|_{z=1}$$ or $$\left. \frac{1}{n!} \prod_{k=0}^{n-1} \sum_{m=0}^k z^m \sum_{k=0}^{n-1} \frac{\sum_{m=1}^k m z^{m-1} }{\sum_{m=0}^k z^m } \right|_{z=1}$$ which is $$\sum_{k=0}^{n-1} \frac{\sum_{m=1}^k m }{k+1} = \frac{1}{4} n (n-1).$$
Let $u_{n, k}$ be the coefficients of your pyramid, so that $u_{n, k}$ where $0\le k\le n(n-1)/2$ is the $n$th row. Then if you are looking for a recurrence like the one we have for Pascal's triangle, it is given by $$u_{n,k} = \begin{cases} 1 \quad\text{if} \quad k=0 \\ \sum_{m=k-n+1}^k u_{n-1,m} \quad \text{otherwise.} \end{cases}$$ – Marko Riedel Nov 26 '12 at 20:37
Let $n$ be the size of the list, and $k \le n(n-1)/2$ be the number of swaps. The number you are looking for is the number of ways to write $$k = x_1+x_2+\ldots+x_n$$ such that each $x_i \in [0, i)$. Each $x_i$ corresponds to the number of spaces that the $i$-th element in the list is "bubbled" to the left. For instance, for $n=4$ and $k=2$, the five possibilities are $$\begin{eqnarray} 2&=&0+0+0+2 \\ 2&=&0+0+1+1 \\ 2&=&0+0+2+0 \\ 2&=&0+1+0+1 \\ 2&=&0+1+1+0. \\ \end{eqnarray}$$ The symmetry noted in the question corresponds to the mapping $x_i \rightarrow i-1-x_i$ and $k\rightarrow \sum_{i}(i-1) - k = n(n-1)/2-k$.
Well, you could use the generating function, which is $f_{n}(z)=(1-z)^{-n}\prod_{k=1}^{n}(1-z^{k})$. – mjqxxxx Nov 26 '12 at 18:56