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
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Mar 15 2013
EXTENSIONS
Formula and terms a(15) onward from Max Alekseyev, Aug 13 2013
STATUS
approved