A264082
Total number of inversions in all set partitions of [n].
Original entry on oeis.org
0, 0, 0, 1, 10, 74, 504, 3383, 23004, 160444, 1154524, 8594072, 66243532, 528776232, 4369175522, 37343891839, 329883579768, 3008985817304, 28312886239136, 274561779926323, 2741471453779930, 28159405527279326, 297291626845716642, 3223299667111201702
Offset: 0
a(3) = 1: one inversion in 13|2.
a(4) = 10: one inversion in each of 124|3, 13|24, 13|2|4, 1|24|3, and two inversions in each of 134|2, 14|23, 14|2|3.
-
b:= proc(n, t) option remember; `if`(n=0, [1, 0], add((p-> p+
[0, p[1]*(j*t/2)])(b(n-j, t+j-1))*binomial(n-1, j-1), j=1..n))
end:
a:= n-> b(n, 0)[2]:
seq(a(n), n=0..23); # Alois P. Heinz, Feb 20 2025
-
b[n_, t_] := b[n, t] = If[n == 0, {1, 0}, Sum[Function[p, p+{0, p[[1]]*(j*t/2)}][b[n-j, t+j-1]]*Binomial[n-1, j-1], {j, 1, n}]];
a[n_] := b[n, 0][[2]];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, May 21 2025, after Alois P. Heinz *)
A271370
Total number of inversions in all partitions of n.
Original entry on oeis.org
0, 0, 0, 1, 3, 9, 18, 38, 68, 120, 200, 326, 508, 785, 1179, 1741, 2532, 3633, 5141, 7199, 9972, 13680, 18618, 25116, 33642, 44738, 59139, 77653, 101444, 131751, 170320, 219049, 280553, 357652, 454254, 574507, 724135, 909265, 1138169, 1419737, 1765884, 2189441
Offset: 0
a(3) = 1: one inversion in 21.
a(4) = 3: one inversion in 31, and two inversions in 211.
-
b:= proc(n, i, t) option remember; `if`(n=0, [1, 0], `if`(i<1, 0,
add((p-> p+[0, p[1]*j*t])(b(n-i*j, i-1, t+j)), j=0..n/i)))
end:
a:= n-> b(n$2, 0)[2]:
seq(a(n), n=0..60);
-
b[n_, i_, t_] := b[n, i, t] = If[n==0, {1, 0}, If[i<1, 0, Sum[Function[p, If[p === 0, 0, p+{0, p[[1]]*j*t}]][b[n-i*j, i-1, t+j]], {j, 0, n/i}]]];
a[n_] := b[n, n, 0][[2]]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Feb 03 2017, translated from Maple *)
A271372
Total number of inversions in all compositions of n into distinct parts.
Original entry on oeis.org
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
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.
-
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);
-
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 *)
A189073
Triangle read by rows: T(n,k) is the number of inversions in k-compositions of n for n >= 3, 2 <= k <= n-1.
Original entry on oeis.org
1, 1, 3, 2, 6, 6, 2, 12, 18, 10, 3, 18, 42, 40, 15, 3, 27, 78, 110, 75, 21, 4, 36, 132, 240, 240, 126, 28, 4, 48, 204, 460, 600, 462, 196, 36, 5, 60, 300, 800, 1290, 1302, 812, 288, 45, 5, 75, 420, 1300, 2490, 3108, 2548, 1332, 405, 55, 6, 90, 570, 2000, 4440, 6594, 6692, 4608, 2070, 550, 66
Offset: 3
Triangle begins:
1;
1, 3;
2, 6, 6;
2, 12, 18, 10;
3, 18, 42, 40, 15;
3, 27, 78, 110, 75, 21;
4, 36, 132, 240, 240, 126, 28;
4, 48, 204, 460, 600, 462, 196, 36;
5, 60, 300, 800, 1290, 1302, 812, 288, 45;
5, 75, 420, 1300, 2490, 3108, 2548, 1332, 405, 55;
6, 90, 570, 2000, 4440, 6594, 6692, 4608, 2070, 550, 66;
...
T(5,3) = 6 because we have: 3+1+1, 1+3+1, 1+1+3, 2+2+1, 2+1+2, 1+2+2 having 2,1,0,2,1,0 inversions respectively. - _Geoffrey Critzer_, Mar 19 2014
-
T:= proc(n, k) option remember;
if k=2 then floor((n-1)/2)
elif k>=n then 0
else T(n-1, k) +k/(k-2) *T(n-1, k-1)
fi
end:
seq(seq(T(n, k), k=2..n-1), n=3..13); # Alois P. Heinz, Apr 17 2011
-
T[n_, k_] := T[n, k] = Which[k == 2, Floor[(n-1)/2], k >= n, 0, True, T[n-1, k] + k/(k-2)*T[n-1, k-1]]; Table[Table[T[n, k], {k, 2, n-1}], {n, 3, 13}] // Flatten (* Jean-François Alcover, Jan 14 2014, after Alois P. Heinz *)
Showing 1-4 of 4 results.
Comments