cp's OEIS Frontend

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

%I A271372 #15 May 29 2018 10:41:09
%S A271372 0,0,0,1,1,2,11,12,21,31,112,122,212,294,456,1147,1381,2144,3059,4494,
%T A271372 6081,13597,15928,24716,33728,49260,65016,93229,169249,210206,304979,
%U A271372 417600,584037,779731,1076824,1409102,2418068,2950722,4213584,5581351,7779829
%N A271372 Total number of inversions in all compositions of n into distinct parts.
%H A271372 Alois P. Heinz, <a href="/A271372/b271372.txt">Table of n, a(n) for n = 0..6000</a>
%H A271372 Wikipedia, <a href="https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)">Inversion (discrete mathematics)</a>
%F A271372 a(n) = Sum_{k>=1} A001809(k) * A008289(n,k).
%e A271372 a(3) = 1: 21.
%e A271372 a(4) = 1: 31.
%e A271372 a(5) = 2: 41, 32.
%e A271372 a(6) = 11: one inversion in each of 51, 132, 42, 213, two inversions in each of 231, 312, three inversions in 321.
%p A271372 b:= proc(n, i, t) option remember; `if`(n>i*(i+1)/2, 0,
%p A271372       `if`(n=0, t!*t*(t-1)/4, b(n, i-1, t)+
%p A271372       `if`(i>n, 0, b(n-i, i-1, t+1))))
%p A271372     end:
%p A271372 a:= n-> b(n$2, 0):
%p A271372 seq(a(n), n=0..60);
%t A271372 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]]]];
%t A271372 a[n_] := b[n, n, 0];
%t A271372 Table[a[n], {n, 0, 60}] (* _Jean-François Alcover_, May 29 2018, from Maple *)
%Y A271372 Cf. A001809, A008289, A032020, A189052, A271371.
%K A271372 nonn
%O A271372 0,6
%A A271372 _Alois P. Heinz_, Apr 05 2016