|
|
A216239
|
|
Total number of inversions in all derangement permutations of [n].
|
|
6
|
|
|
0, 0, 1, 4, 34, 260, 2275, 21784, 228676, 2614296, 32372805, 431971100, 6182204006, 94495208444, 1536740258599, 26498747241680, 482990781797000, 9279452377499504, 187442757190618761, 3971627425918503156, 88084356619901450410, 2040857112777615061300
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
LINKS
|
|
|
FORMULA
|
a(n) = SUM(k=0..n-2, (-1)^k * n!/k! * (3*n+k)*(n-k-1) )/12. - Max Alekseyev, Aug 13 2013
|
|
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:
|
|
MATHEMATICA
|
|
|
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
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|