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,6

Links

Alois P. Heinz, Table of n, a(n) for n = 0..6000

Wikipedia, Inversion (discrete mathematics)

Formula

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

Example

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.

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 *)

Crossrefs

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

Sequence in context: A214215 A376637 A136999 * A053880 A063112 A038113

Adjacent sequences: A271369 A271370 A271371 * A271373 A271374 A271375

Keyword

nonn

Author

Alois P. Heinz, Apr 05 2016

Status

approved