0,4

T(n,k) is also the number of permutations with Kendall tau distance ("bubble-sort distance") to the identity permutation being at most k. This is the number of swaps performed by the bubble-sort algorithm to sort the sequence.

The above only gives T(n,k) for k<=n(n-1)/2, but T(n,k)=n! for all k>=n(n-1)/2.

T(n,k) = sum_{i s.t. n-i<=k} T(n-1, k-(n-i))

= sum_{i=max(1,n-k) to n} T(n-1, k-n+i)

= sum_{j=max(k-n+1,0) to n} T(n-1, j)

T(n,k) = T(n,k-1) + T(n-1,k) - T(n-1,k-n), taking T(n,k)=0 for k<0.

Also, T(n,k) = n! - T(n, n(n-1)/2-k-1)

For k<=n, T(n,k) = A008302(n+1,k).

T(3,2)=5 because there are 5 permutations of {1,2,3} with at most 2 inversions: (1,2,3) with 0 inversions, (1,3,2), (2,1,3) with 1 inversion each, (2,3,1), (3,1,2) with 2 inversions each.

T(n,0)=1 because there is exactly 1 permutation (the identity permutation) with no inversions,

T(n,k) = n! for all k >= n(n-1)/2 because all permutations have at most n(n-1)/2 inversions.

(Python) ct = {(0, 0): 1}

def c(n, k):

....if k<0: return 0

....k = min(k, n*(n-1)/2)

....if (n, k) in ct: return ct[(n, k)]

....ct[(n, k)] = c(n, k-1) + c(n-1, k) - c(n-1, k-n)

....return ct[(n, k)]

Partial sums of A008302.

Sequence in context: A063705 A137655 A167595 this_sequence A058202 A127201 A006769

Adjacent sequences: A161166 A161167 A161168 this_sequence A161170 A161171 A161172

easy,nonn,tabl

R. Shreevatsa (shreevatsa.public(AT)gmail.com), Jun 04 2009