8
$\begingroup$

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.

  • 0
    @ThomasAndrews Ah. Ignore that part then.2012-11-26

2 Answers 2

7

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).$

  • 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}$2012-11-26
2

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$.

  • 0
    So then suppose I have n=45, or n=52. How might I get the first few terms of the list using the generating function? Could you include that in your answer?2012-11-26