A211606 -id:A211606 - cp's OEIS frontend

A216239 Total number of inversions in all derangement permutations of [n].

0, 0, 1, 4, 34, 260, 2275, 21784, 228676, 2614296, 32372805, 431971100, 6182204006, 94495208444, 1536740258599, 26498747241680, 482990781797000, 9279452377499504, 187442757190618761, 3971627425918503156, 88084356619901450410, 2040857112777615061300

Offset: 0

Alois P. Heinz, Mar 15 2013

nonn

			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

Cf. A000166, A001809, A161124, A211606, A227404, A228924, A337193.

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

a(n) = SUM(k=0..n-2, (-1)^k * n!/k! * (3*n+k)*(n-k-1) )/12. - Max Alekseyev, Aug 13 2013
a(n) = ( (3*n^2-n+1)*A000166(n) + (n-1)*(-1)^n )/12. - Max Alekseyev, Aug 14 2013
a(n) = Sum_{k>=1} A228924(n,k) * k. - Alois P. Heinz, Sep 22 2013
a(n) ~ n! * n^2 / (4*exp(1)). - Vaclav Kotesovec, Sep 10 2014

Formula and terms a(15) onward from Max Alekseyev, Aug 13 2013

A161124 Number of inversions in all fixed-point-free involutions of {1,2,...,2n}.

Original entry on oeis.org

0, 1, 12, 135, 1680, 23625, 374220, 6621615, 129729600, 2791213425, 65472907500, 1663666579575, 45537716624400, 1336089255125625, 41837777148667500, 1392813754566609375, 49126088694402720000, 1830138702650463830625, 71812362934450726087500

Offset: 0

Emeric Deutsch, Jun 05 2009

nonn

Also the sum of the major indices of all fixed-point-free involutions of {1,2,...,2n}. Example: a(2)=12 because the fixed-point-free involutions 2143, 3412, and 4321 have major indices 4, 2, and 6, respectively.
a(n) = Sum(k*A161123(n,k), k>=0).
For n > 0, a(n) is also the determinant absolute value of the symmetric n X n matrix M defined by M(i,j) = max(i,j)^2 for 1 <= i,j <= n. - Enrique Pérez Herrero, Jan 14 2013

			a(2) = 12 because the fixed-point-free involutions 2143, 3412, and 4321 have 2, 4, and 6 inversions, respectively.

Alois P. Heinz, Table of n, a(n) for n = 0..200
E. Pérez Herrero, Max Determinant, Psychedelic Geometry Blogspot, 15 Jan 2013

Cf. A161123.

Cf. A051125, A181983, A211606.

seq(n^2*factorial(2*n)/(factorial(n)*2^n), n = 0 .. 18);

nn=40;Prepend[Select[Range[0,nn]!CoefficientList[Series[(x^2/2+x^4/4)Exp[x^2/2],{x,0,nn}],x],#>0&],0] (* Geoffrey Critzer, Mar 03 2013 *)
Table[n^2 (2n-1)!!,{n,0,20}] (* Harvey P. Dale, Jan 05 2014 *)

a(n) = n^2*(2n-1)!!.
a(n) = n^2*A001147(n). - Enrique Pérez Herrero, Jan 14 2013
a(n) = (2n)! * [x^(2n)] (x^2/2 + x^4/4)*exp(x^2/2). - Geoffrey Critzer, Mar 03 2013
D-finite with recurrence a(n) +(-2*n-7)*a(n-1) +(8*n-3)*a(n-2) +(-2*n+5)*a(n-3)=0. - R. J. Mathar, Jul 26 2022

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

Alois P. Heinz, Apr 03 2016

nonn

Each set partition is written as a sequence of blocks, ordered by the smallest elements in the blocks.

			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.

Alois P. Heinz, Table of n, a(n) for n = 0..573
Wikipedia, Inversion (discrete mathematics)
Wikipedia, Partition of a set

Cf. A001809, A125810, A189052, A211606, A216239, A240796, A271370.

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

a(n) = Sum_{k>0} k * A125810(n,k).

A337193 Total number of inversions in all permutations of [n] where the descent set equals the subset of odd elements in [n-1].

Original entry on oeis.org

0, 0, 1, 3, 18, 80, 495, 2856, 20244, 142848, 1167885, 9729280, 90858438, 872361984, 9193900443, 99947258880, 1175452387560, 14270843322368, 185456745850329, 2487099677147136, 35413726451731770, 519907295578030080, 8052572864648861703, 128451121643116822528

Offset: 0

Alois P. Heinz, Aug 18 2020

nonn

			a(3) = 3, because in the A000111(3) = 2 permutations 213, 312 there are 3 inversions: (2,1), (3,1), (3,2).
a(4) = 18, because in the A000111(4) = 5 permutations 2143, 3142, 3241, 4132, 4231 there are 18 inversions: (2,1), (4,3), (3,1), (3,2), (4,2), (3,2), (3,1), (2,1), (4,1), (4,1), (4,3), (4,2), (3,2), (4,2), (4,3), (4,1), (2,1), (3,1).

Alois P. Heinz, Table of n, a(n) for n = 0..483
Wikipedia, Inversion
Wikipedia, Permutation

Cf. A000111, A001809, A211606, A216239, A337126.

b:= proc(u, o, t) option remember; `if`(u+o=0, [1, 0], add((p-> [0,
      `if`(t=0, o-1+j, u-j)*p[1]]+p)(b(o-1+j, u-j, 1-t)), j=1..u))
    end:
a:= n-> b(n, 0$2)[2]:
seq(a(n), n=0..30);

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}]]];
a[n_] := With[{cc = CoefficientList[b[n, 0, 0], x]}, cc.Range[0, Length[cc]-1] ];
a /@ Range[0, 30] (* Jean-François Alcover, Jan 02 2021, after Alois P. Heinz in A337126 *)

a(n) = Sum_{k=1..ceiling((n-1)^2/2)} k * A337126(n,k).
From Vaclav Kotesovec, Aug 31 2020: (Start)
a(n) ~ n! * 2^n * n^2 / Pi^(n+1).
a(n) ~ 2^(n + 1/2) * n^(n + 5/2) / (Pi^(n + 1/2) * exp(n)). (End)

A227404 Total number of inversions in all permutations of order n consisting of a single cycle.

Original entry on oeis.org

0, 0, 1, 4, 22, 140, 1020, 8400, 77280, 786240, 8769600, 106444800, 1397088000, 19718899200, 297859161600, 4794806016000, 81947593728000, 1482030950400000, 28277150533632000, 567677135241216000, 11961768206868480000, 263969867887165440000

Offset: 0

Geoffrey Critzer, Sep 21 2013

nonn

The formula trivially follows from the observation that every pair of elements iMax Alekseyev, Jan 05 2018

a(n) is the number of ways to partition a (n+1)X(n+1) square, with the upper left hand corner missing, into ribbons of size n, see Alexandersson, Jordan. - Per W. Alexandersson, Jun 02 2020

			a(3) = 4 because the cyclic 3-permutations: (1,2,3), (1,3,2) written in one line (sequence) notation: {2,3,1}, {3,1,2} have 2 + 2 = 4 inversions.

Alois P. Heinz, Table of n, a(n) for n = 0..449
Per Alexandersson, Linus Jordan, Enumeration of border-strip decompositions, arXiv:1805.09778 [math.CO], 2018.
Per Alexandersson, Linus Jordan, Enumeration of border-strip decompositions, Journal of Integer Sequences, Vol. 22 (2019), Article 19.4.5.

Cf. A001809, A211606, A216239.

Table[Total[Map[Inversions,Map[FromCycles,Map[List, Map[Prepend[#,n]&, Permutations[n-1]]]]]],{n,1,8}]

For n>2, a(n) = n! * (3*n-1)/12. - Vaclav Kotesovec, Feb 14 2014

a(13)-a(15) from Alois P. Heinz, Sep 26 2013

Terms a(16) and beyond from Max Alekseyev, Jan 05 2018

A213910 Irregular triangle read by rows: T(n,k) is the number of involutions of length n that have exactly k inversions; n>=0, 0<=k<=binomial(n,2).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 0, 1, 1, 3, 1, 2, 1, 1, 1, 1, 4, 3, 3, 4, 2, 4, 1, 3, 0, 1, 1, 5, 6, 5, 9, 5, 10, 5, 9, 4, 7, 3, 3, 2, 1, 1, 1, 6, 10, 9, 16, 13, 19, 17, 19, 19, 17, 19, 13, 17, 7, 13, 3, 8, 1, 4, 0, 1, 1, 7, 15, 16, 26, 29, 34, 43, 39, 54, 41, 61, 40, 62, 36, 58, 28, 47, 21, 34, 15, 21, 10, 11, 6, 4, 3, 1, 1

Offset: 0

Geoffrey Critzer, Mar 04 2013

			T(4,3) = 2 because we have: (3,2,1,4), (1,4,3,2).
Triangle T(n,k) begins:
  1;
  1;
  1, 1;
  1, 2, 0, 1;
  1, 3, 1, 2, 1, 1,  1;
  1, 4, 3, 3, 4, 2,  4, 1, 3, 0, 1;
  1, 5, 6, 5, 9, 5, 10, 5, 9, 4, 7, 3, 3, 2, 1, 1;
  ...

Alois P. Heinz, Rows n = 0..40, flattened

Cf. A008302 (permutations of [n] with k inversions).

Cf. A000085 (row sums), A211606, A214086 (diagonal).

T:= proc(n) option remember; local f, g, j; if n<2 then 1 else
      f, g:= [T(n-1)], [T(n-2)]; for j to 2*n-3 by 2 do
      f:= zip((x, y)->x+y, f, [0$j, g[]], 0) od; f[] fi
    end:
seq(T(n), n=0..10);  # Alois P. Heinz, Mar 05 2013

Needs["Combinatorica`"];
Table[Distribution[Map[Inversions,Involutions[n]],Range[0,Binomial[n,2]]],{n,0,9}]//Flatten
(* Second program: *)
zip[f_, x_List, y_List, z_] := With[{m = Max[Length[x], Length[y]]}, f[PadRight[x, m, z], PadRight[y, m, z]]];
T[n_] := T[n] = Module[{f, g, j}, If[n < 2, Return@{1}, f = T[n-1]; g = T[n-2]; For[j = 1, j <= 2*n - 3, j += 2, f = zip[Plus, f, Join[Table[0, {j}], g], 0]]]; f];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 04 2023, after Alois P. Heinz *)

Sum_{k>=0} T(n,k)*k = A211606(n).

T(n,k) = T(n-1,k) + Sum_{j=1..n-1} T(n-2,k-2*(n-j)+1) for n>=0, k>0; T(n,k) = 0 for n<0 or k<0; T(n,0) = 1 for n>=0. - Alois P. Heinz, Mar 07 2013

cp's OEIS Frontend

A216239 Total number of inversions in all derangement permutations of [n].

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A161124 Number of inversions in all fixed-point-free involutions of {1,2,...,2n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A264082 Total number of inversions in all set partitions of [n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A337193 Total number of inversions in all permutations of [n] where the descent set equals the subset of odd elements in [n-1].

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A227404 Total number of inversions in all permutations of order n consisting of a single cycle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A213910 Irregular triangle read by rows: T(n,k) is the number of involutions of length n that have exactly k inversions; n>=0, 0<=k<=binomial(n,2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula