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

Links

Max Alekseyev and Alois P. Heinz, Table of n, a(n) for n = 0..450 (first 100 terms from Max Alekseyev)

Wikipedia, Derangement

Wikipedia, Inversion

Formula

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

Example

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.

Maple

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

Mathematica

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

Prog

(PARI) A216239(n) = sum(k=0, n-2, (-1)^k * n!/k! * (3*n+k) * (n-k-1) )/12; /* Max Alekseyev, Aug 13 2013 */

Crossrefs

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

Sequence in context: A049293 A198687 A116430 * A335667 A201684 A155628

Adjacent sequences: A216236 A216237 A216238 * A216240 A216241 A216242

Keyword

nonn

Author

Alois P. Heinz, Mar 15 2013

Extensions

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

Status

approved