title: Dynamic Programming: Number of ways to get at least N bubble sort swaps?
body: <p>Let's say I have an array of elements for which a total ordering exists.  The bubble sort distance is the number of swaps that it would take to sort the array if I were using a bubble sort.  What is an efficient (will probably involve dynamic programming) way to calculate the number of possible permutations of this array that will have a bubble sort distance less than or equal to some pre-specified number?</p>
  
  <p>If it simplifies the problem, you may assume that all elements of the array are unique (no ties).</p>