login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A216239 Total number of inversions in all derangement permutations of [n]. 5
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

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.

Sequence in context: A049293 A198687 A116430 * A201684 A155628 A036352

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 17 15:28 EDT 2019. Contains 324194 sequences. (Running on oeis4.)