

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.


LINKS

Table of n, a(n) for n=0..60.
D. Wang, A. Mazumdar and G. W. Wornell, A RateDistortion Theory for Permutation Spaces, 2013.


FORMULA

T(n,k) = Sum_{i s.t. ni<=k} T(n1, k(ni));
T(n,k) = Sum_{i=max(1,nk)..n} T(n1, kn+i);
T(n,k) = Sum_{j=max(kn+1,0)..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: A167595 A328600 A179382 * A239738 A058202 A327452
Adjacent sequences: A161166 A161167 A161168 * A161170 A161171 A161172


KEYWORD

easy,nonn,tabf


AUTHOR

Shreevatsa R, Jun 04 2009


STATUS

approved



