Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
show 2 more comments

2 Answers

up vote 6 down vote accepted

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

share|improve this answer
    
In that case, what would our list look like for any n? I got the same thing for the expected number of swaps... but how could we find a generalization for the nth row in the pyramid I suggested? –  Johann Linus Nov 26 '12 at 17:49
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
add comment

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

share|improve this answer
    
@mjqxxxx Is there any way to make that more explicit? –  Johann Linus Nov 26 '12 at 16:50
    
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
    
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? –  Johann Linus Nov 26 '12 at 19:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.