This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 ("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. REFERENCES D. Wang, A. Mazumdar and G. W. Wornell, A Rate-Distortion Theory for Permutation Spaces, 2013; http://www.ece.umn.edu/~arya/papers/rd_isit13.pdf LINKS FORMULA 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). 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(n-1)/2 because all permutations have at most n(n-1)/2 inversions. PROG (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)] 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 16 09:54 EDT 2018. Contains 313791 sequences. (Running on oeis4.)