cp's OEIS Frontend

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

%I A161169 #26 Feb 21 2025 18:38:37
%S A161169 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,
%T A161169 1,6,20,49,98,169,259,360,461,551,622,671,700,714,719,720,1,7,27,76,
%U A161169 174,343,602,961,1416,1947,2520,3093,3624,4079,4438,4697,4866,4964,5013
%N A161169 Triangle read by rows: T(n,k) = number of permutations of {1..n} with at most k inversions.
%C A161169 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.
%C A161169 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.
%H A161169 Alois P. Heinz, <a href="/A161169/b161169.txt">Rows n = 0..50, flattened</a>
%H A161169 D. Wang, A. Mazumdar and G. W. Wornell, <a href="http://www.ece.umn.edu/~arya/papers/rd_isit13.pdf">A Rate-Distortion Theory for Permutation Spaces</a>, 2013.
%F A161169 T(n,k) = Sum_{i s.t. n-i<=k} T(n-1, k-(n-i));
%F A161169 T(n,k) = Sum_{i=max(1,n-k)..n} T(n-1, k-n+i);
%F A161169 T(n,k) = Sum_{j=max(k-n+1,0)..n} T(n-1, j).
%F A161169 T(n,k) = T(n,k-1) + T(n-1,k) - T(n-1,k-n), taking T(n,k)=0 for k<0.
%F A161169 Also, T(n,k) = n! - T(n, n(n-1)/2-k-1).
%F A161169 For k<=n, T(n,k) = A008302(n+1,k).
%F A161169 G.f.: (1/(1-x))*Product_{j=1..n} (1-x^j)/(1-x) = Sum_{k>=0} T(n,k) x^k. - _Alejandro H. Morales_, Apr 04 2024
%e A161169 Triangle begins:
%e A161169   1;
%e A161169   1;
%e A161169   1, 2;
%e A161169   1, 3,  5,  6;
%e A161169   1, 4,  9, 15, 20,  23,  24;
%e A161169   1, 5, 14, 29, 49,  71,  91, 106, 115, 119, 120;
%e A161169   1, 6, 20, 49, 98, 169, 259, 360, 461, 551, 622, 671, 700, 714, 719, 720;
%e A161169   ...
%e A161169 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.
%e A161169 T(n,0)=1 because there is exactly 1 permutation (the identity permutation) with no inversions,
%e A161169 T(n,k) = n! for all k >= n(n-1)/2 because all permutations have at most n(n-1)/2 inversions.
%o A161169 (Python)
%o A161169 ct = {(0,0): 1}
%o A161169 def c(n,k):
%o A161169     if k<0: return 0
%o A161169     k = min(k, n*(n-1)/2)
%o A161169     if (n, k) in ct: return ct[(n, k)]
%o A161169     ct[(n, k)] = c(n, k-1) + c(n-1, k) - c(n-1, k-n)
%o A161169     return ct[(n, k)]
%Y A161169 Partial sums of A008302.
%K A161169 easy,nonn,tabf
%O A161169 0,4
%A A161169 _Shreevatsa R_, Jun 04 2009