

A161169


Triangle read by rows: T(n,k) = number of permutations of {1..n} with at most k inversions.


1



1, 1, 1, 2, 1, 3, 5, 6, 1, 4, 9, 15, 20, 23, 24, 1, 5, 14, 29, 49, 71, 91, 106, 115, 119, 120, 1, 6, 20, 49, 98, 169, 259, 360, 461, 551, 622, 671, 700, 714, 719, 720, 1, 7, 27, 76, 174, 343, 602, 961, 1416, 1947, 2520, 3093, 3624, 4079, 4438, 4697, 4866, 4964, 5013
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

T(n,k) is also the number of permutations with Kendall tau distance ("bubblesort distance") to the identity permutation being at most k. This is the number of swaps performed by the bubblesort algorithm to sort the sequence.
The above only gives T(n,k) for k<=n(n1)/2, but T(n,k)=n! for all k>=n(n1)/2.


REFERENCES

D. Wang, A. Mazumdar and G. W. Wornell, A RateDistortion Theory for Permutation Spaces, 2013; http://www.ece.umn.edu/~arya/papers/rd_isit13.pdf


LINKS

Table of n, a(n) for n=0..60.


FORMULA

T(n,k) = sum_{i s.t. ni<=k} T(n1, k(ni))
= sum_{i=max(1,nk) to n} T(n1, kn+i)
= sum_{j=max(kn+1,0) to n} T(n1, j)
T(n,k) = T(n,k1) + T(n1,k)  T(n1,kn), taking T(n,k)=0 for k<0.
Also, T(n,k) = n!  T(n, n(n1)/2k1)
For k<=n, T(n,k) = A008302(n+1,k).


EXAMPLE

Triangle begins:
1,
1,
1, 2,
1, 3, 5, 6,
1, 4, 9, 15, 20, 23, 24,
1, 5, 14, 29, 49, 71, 91, 106, 115, 119, 120,
1, 6, 20, 49, 98, 169, 259, 360, 461, 551, 622, 671, 700, 714, 719, 720,
...
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(n1)/2 because all permutations have at most n(n1)/2 inversions.


PROG

(Python) ct = {(0, 0): 1}
def c(n, k):
....if k<0: return 0
....k = min(k, n*(n1)/2)
....if (n, k) in ct: return ct[(n, k)]
....ct[(n, k)] = c(n, k1) + c(n1, k)  c(n1, kn)
....return ct[(n, k)]


CROSSREFS

Partial sums of A008302.
Sequence in context: A296064 A167595 A179382 * A239738 A058202 A257982
Adjacent sequences: A161166 A161167 A161168 * A161170 A161171 A161172


KEYWORD

easy,nonn,tabf


AUTHOR

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


STATUS

approved



