A271372 Total number of inversions in all compositions of n into distinct parts.

0, 0, 0, 1, 1, 2, 11, 12, 21, 31, 112, 122, 212, 294, 456, 1147, 1381, 2144, 3059, 4494, 6081, 13597, 15928, 24716, 33728, 49260, 65016, 93229, 169249, 210206, 304979, 417600, 584037, 779731, 1076824, 1409102, 2418068, 2950722, 4213584, 5581351, 7779829

Offset: 0

Author

Alois P. Heinz, Apr 05 2016

Keywords

• nonn

Examples

			a(3) = 1: 21.
a(4) = 1: 31.
a(5) = 2: 41, 32.
a(6) = 11: one inversion in each of 51, 132, 42, 213, two inversions in each of 231, 312, three inversions in 321.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..6000
• Wikipedia, Inversion (discrete mathematics)

Crossrefs

Cf. A001809, A008289, A032020, A189052, A271371.

Programs

Maple

b:= proc(n, i, t) option remember; `if`(n>i*(i+1)/2, 0,
      `if`(n=0, t!*t*(t-1)/4, b(n, i-1, t)+
      `if`(i>n, 0, b(n-i, i-1, t+1))))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..60);

Mathematica

b[n_, i_, t_] := b[n, i, t] = If[n > i*(i + 1)/2, 0, If[n == 0, t!*t*(t - 1)/4, b[n, i - 1, t] + If[i > n, 0, b[n - i, i - 1, t + 1]]]];
a[n_] := b[n, n, 0];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, May 29 2018, from Maple *)

Formula

a(n) = Sum_{k>=1} A001809(k) * A008289(n,k).