A211606
Total number of inversions over all involutions of length n.
Original entry on oeis.org
0, 0, 1, 5, 26, 110, 490, 2086, 9240, 40776, 185820, 855580, 4048616, 19455800, 95773496, 479581480, 2454041920, 12776826816, 67849286160, 366455145936, 2015621873440, 11268605368160, 64074235576736, 370040657037920, 2171138049287296, 12928631894588800, 78139702237771200
Offset: 0
a(3) = 5 because in the involutions of {1,2,3}: (given in word form) 213, 321, 132, 123, there are respectively 1 + 3 + 1 + 0 = 5 inversions.
- R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 339.
-
a:= proc(n) option remember; `if`(n<3, n*(n-1)/2,
n*((n-2)*(9*n-7) *a(n-1) +(n-1)*(9*n^2-13*n+2) *a(n-2))/
((n-2)*(9*n^2-31*n+24)))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Feb 12 2013
-
(* first do *) Needs["Combinatorica`"] // Quiet (* then *)
Table[Total[Map[Inversions, Involutions[n]]], {n, 0, 10}]
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ (x^2/2 + x^3/3 + x^4/4) Exp[x + x^2/2], {x, 0, n}]]; (* Michael Somos, Jun 03 2019 *)
-
{a(n) = if( n<0, 0, n! * polcoeff( (x^2/2 + x^3/3 + x^4/4) * exp(x + x^2/2 + x * O(x^n)), n))}; /* Michael Somos, Jun 03 2019 */
A216239
Total number of inversions in all derangement permutations of [n].
Original entry on oeis.org
0, 0, 1, 4, 34, 260, 2275, 21784, 228676, 2614296, 32372805, 431971100, 6182204006, 94495208444, 1536740258599, 26498747241680, 482990781797000, 9279452377499504, 187442757190618761, 3971627425918503156, 88084356619901450410, 2040857112777615061300
Offset: 0
a(2) = 1: (2,1) has 1 inversion.
a(3) = 4: (2,3,1), (3,1,2) have 2+2 = 4 inversions.
a(4) = 34: (2,1,4,3), (2,3,4,1), (2,4,1,3), (3,1,4,2), (3,4,1,2), (3,4,2,1), (4,1,2,3), (4,3,1,2), (4,3,2,1) have 2+3+3+3+4+5+3+5+6 = 34 inversions.
- Max Alekseyev and Alois P. Heinz, Table of n, a(n) for n = 0..450 (first 100 terms from Max Alekseyev)
- Moussa Ahmia, José L. Ramírez, and Diego Villamizar, Inversions in Colored Permutations, Derangements, and Involutions, arXiv:2505.01550 [math.CO], 2025. See p. 12.
- Wikipedia, Derangement
- Wikipedia, Inversion
-
v:= proc(l) local i; for i to nops(l) do if l[i]=i then return 0 fi od;
add(add(`if`(l[i]>l[j], 1, 0), j=i+1..nops(l)), i=1..nops(l)-1)
end:
a:= n-> add(v(d), d=combinat[permute](n)):
seq(a(n), n=0..8);
# second Maple program:
a:= proc(n) option remember; `if`(n<3, n*(n-1)/2,
n*((6*n^3-26*n^2+31*n-9)*a(n-1)+(n-1)*
(6*n^2-8*n+1)*a(n-2))/((n-2)*(15-20*n+6*n^2)))
end:
seq(a(n), n=0..25); # Alois P. Heinz, Aug 13 2013
-
A216239[n_] := (1/12)*n*(3*(-1)^n*n + (n*(3*n - 1) + 1)*Subfactorial[n-1]); Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Feb 05 2015, after Max Alekseyev *)
-
A216239(n) = sum(k=0,n-2, (-1)^k * n!/k! * (3*n+k) * (n-k-1) )/12; /* Max Alekseyev, Aug 13 2013 */
A337126
Irregular triangular array read by rows. T(n,k) is the number of permutations of {1,2,...,n} with descent set {1,3,5,...,m} (where m is the greatest odd integer less than n) that have exactly k inversions, n=0, k=0, or n>0, 0<=k<=ceiling((n-1)^2/2).
Original entry on oeis.org
1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 2, 1, 0, 0, 1, 2, 3, 4, 3, 2, 1, 0, 0, 0, 1, 2, 5, 7, 9, 10, 10, 8, 5, 3, 1, 0, 0, 0, 1, 3, 7, 13, 19, 26, 32, 35, 35, 32, 26, 19, 13, 7, 3, 1, 0, 0, 0, 0, 1, 3, 9, 18, 32, 50, 72, 95, 117, 134, 143, 145, 138, 122, 101, 78, 55, 36, 21, 10, 4, 1
Offset: 0
Triangle T(n,k) begins:
1;
1;
0, 1;
0, 1, 1;
0, 0, 1, 1, 2, 1;
0, 0, 1, 2, 3, 4, 3, 2, 1;
0, 0, 0, 1, 2, 5, 7, 9, 10, 10, 8, 5, 3, 1;
...
T(6,5) = 5 because we have: {2, 1, 5, 4, 6, 3}, {2, 1, 6, 3, 5, 4},
{3, 1, 5, 2, 6, 4}, {3, 2, 4, 1, 6, 5}, {4, 1, 3, 2, 6, 5}.
- R. Stanley, Enumerative Combinatorics, volume 1, second edition, Cambridge University Press (2012), p.295.
-
b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1, add(
x^`if`(t=0, o-1+j, u-j)*b(o-1+j, u-j, 1-t), j=1..u)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..10); # Alois P. Heinz, Aug 17 2020
-
Table[a = Drop[Subsets[Table[i, {i, 1, n - 1, 2}]], 1];f[list_] := (-1)^(Floor[n/2] - Length[list]) QBinomial[n, list[[1]], q] Product[
QBinomial[n - list[[i]], list[[i + 1]] - list[[i]], q], {i, 1,
Length[list] - 1}]; CoefficientList[Expand[FunctionExpand[Total[Map[f, a]] + (-1)^(Floor[n/2])]], q], {n, 0, 8}] // Grid
(* Second program: *)
b[u_, o_, t_] := b[u, o, t] = Expand[If[u + o == 0, 1, Sum[x^If[t == 0, o - 1 + j, u - j]*b[o - 1 + j, u - j, 1 - t], {j, 1, u}]]];
T[n_] := CoefficientList[b[n, 0, 0], x];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Jan 02 2021, after Alois P. Heinz *)
Showing 1-3 of 3 results.