cp's OEIS Frontend

A367313 Triangle read by rows: T(n,k) is the number of permutations of [n] with weighted inversion index k.

%I A367313 #27 Nov 25 2023 18:17:47
%S A367313 1,1,1,1,1,1,2,1,1,1,1,2,3,3,4,3,3,2,1,1,1,1,2,3,5,5,8,9,10,10,12,10,
%T A367313 10,9,8,5,5,3,2,1,1,1,1,2,3,5,7,9,12,16,20,23,28,31,36,38,41,43,44,44,
%U A367313 43,41,38,36,31,28,23,20,16,12,9,7,5,3,2,1,1
%N A367313 Triangle read by rows: T(n,k) is the number of permutations of [n] with weighted inversion index k.
%C A367313 T(n,k) represents two statistics that can be shown to be equal:
%C A367313 (1) Permutations of {1,2,...,n} counted by a "weighted inversion index": for a permutation pi, the weighted inversion index is the sum of i over all pairs i,j with i < j and pi(i) > pi(j).
%C A367313 (2) Partitions lambda with at most n-1 parts counted by weight, where the inequality lambda(i) - lambda(i+1) <= n - i holds for 1 <= i < n (with lambda(n) = 0).
%C A367313 Possible values of this index range from 0 to (n-1)*n*(n+1)/6.  The permutation with the largest weighted inversion index is (n,n-1,...,2,1) and the partition with the largest weight is (n(n-1)/2,(n-1)(n-2)/2,...,3,1).
%C A367313 Let t_n(q) be the sum of T(n,k)q^k, for 0 <= k <= (n-1)*n*(n+1)/6.  Then t_n(q) is the product of (1 - q^(k*(n+1-k)))/(1 - q^k), for 1 <= k <= n-1.
%H A367313 Alois P. Heinz, <a href="/A367313/b367313.txt">Rows n = 0..25, flattened</a>
%F A367313 From _Alois P. Heinz_, Nov 25 2023: (Start)
%F A367313 Sum_{k=0..A050407(n+2)-1} k * T(n,k) = A001754(n+1).
%F A367313 Sum_{k=0..A050407(2n+3)-1} (-1)^k * T(2n+1,k) = A000165(n). (End)
%e A367313 The permutation pi = (2,5,3,1,4) has these inversions, with the given contributions to weighted inversion index:
%e A367313    (2,1), 1
%e A367313    (5,3), 2
%e A367313    (5,1), 2
%e A367313    (5,4), 2
%e A367313    (3,1), 3
%e A367313 The corresponding partition can be created as follows.  For each i <= 5, write the number of j > i with pi(i) > pi(j): (1,3,1,0,0).
%e A367313 For each i, the i-th number in this sequence is at most n-i.
%e A367313 Let lambda(i) be the sum of the values of the sequence starting with the i-th value: lambda = (5,4,1,0,0).
%e A367313 This permutation and partition are counted by T(5,10).  In the product expansion of t_5(q), they correspond to the following choice of terms:
%e A367313    (1 - q^5)/(1 - q) = 1 + q + q^2 + q^3 + q^4:  choose q,
%e A367313    (1 - q^8)/(1 - q^2) = 1 + q^2 + q^4 + q^6:  choose q^6,
%e A367313    (1 - q^9)/(1 - q^3) = 1 + q^3 + q^6:  choose q^3,
%e A367313    (1 - q^8)/(1 - q^4) = 1 + q^4:  choose 1.
%e A367313 Triangle T(n,k) begins:
%e A367313   1;
%e A367313   1;
%e A367313   1, 1;
%e A367313   1, 1, 2, 1, 1;
%e A367313   1, 1, 2, 3, 3, 4, 3, 3,  2,  1,  1;
%e A367313   1, 1, 2, 3, 5, 5, 8, 9, 10, 10, 12, 10, 10, 9, 8, 5, 5, 3, 2, 1, 1;
%e A367313   ...
%Y A367313 Row sums give A000142.
%Y A367313 Row n contains A050407(n+2) terms.
%Y A367313 T(n+1,n) gives A000041(n).
%Y A367313 Cf. A000165, A001754, A175929.
%K A367313 nonn,tabf
%O A367313 0,7
%A A367313 _Todd Simpson_, Nov 13 2023