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