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

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, 1, 1, 2, 3, 5, 7, 9, 12, 16, 20, 23, 28, 31, 36, 38, 41, 43, 44, 44, 43, 41, 38, 36, 31, 28, 23, 20, 16, 12, 9, 7, 5, 3, 2, 1, 1

Offset: 0

Author

Todd Simpson, Nov 13 2023

Keywords

• nonn
• tabf

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.

Examples

			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;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..25, flattened

Crossrefs

Row sums give A000142.

Row n contains A050407(n+2) terms.

T(n+1,n) gives A000041(n).

Cf. A000165, A001754, A175929.

Formula

From Alois P. Heinz, Nov 25 2023: (Start)

Sum_{k=0..A050407(n+2)-1} k * T(n,k) = A001754(n+1).

Sum_{k=0..A050407(2n+3)-1} (-1)^k * T(2n+1,k) = A000165(n). (End)