OFFSET
0,7
COMMENTS
T(n,k) represents two statistics that can be shown to be equal:
(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).
(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).
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).
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.
LINKS
Alois P. Heinz, Rows n = 0..25, flattened
FORMULA
From Alois P. Heinz, Nov 25 2023: (Start)
EXAMPLE
The permutation pi = (2,5,3,1,4) has these inversions, with the given contributions to weighted inversion index:
(2,1), 1
(5,3), 2
(5,1), 2
(5,4), 2
(3,1), 3
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).
For each i, the i-th number in this sequence is at most n-i.
Let lambda(i) be the sum of the values of the sequence starting with the i-th value: lambda = (5,4,1,0,0).
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:
(1 - q^5)/(1 - q) = 1 + q + q^2 + q^3 + q^4: choose q,
(1 - q^8)/(1 - q^2) = 1 + q^2 + q^4 + q^6: choose q^6,
(1 - q^9)/(1 - q^3) = 1 + q^3 + q^6: choose q^3,
(1 - q^8)/(1 - q^4) = 1 + q^4: choose 1.
Triangle T(n,k) begins:
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, 10, 9, 8, 5, 5, 3, 2, 1, 1;
...
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Todd Simpson, Nov 13 2023
STATUS
approved