cp's OEIS Frontend

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

%I A216239 #62 May 08 2025 09:58:49
%S A216239 0,0,1,4,34,260,2275,21784,228676,2614296,32372805,431971100,
%T A216239 6182204006,94495208444,1536740258599,26498747241680,482990781797000,
%U A216239 9279452377499504,187442757190618761,3971627425918503156,88084356619901450410,2040857112777615061300
%N A216239 Total number of inversions in all derangement permutations of [n].
%H A216239 Max Alekseyev and Alois P. Heinz, <a href="/A216239/b216239.txt">Table of n, a(n) for n = 0..450</a> (first 100 terms from Max Alekseyev)
%H A216239 Moussa Ahmia, José L. Ramírez, and Diego Villamizar, <a href="https://arxiv.org/abs/2505.01550">Inversions in Colored Permutations, Derangements, and Involutions</a>, arXiv:2505.01550 [math.CO], 2025. See p. 12.
%H A216239 Wikipedia, <a href="https://en.wikipedia.org/wiki/Derangements">Derangement</a>
%H A216239 Wikipedia, <a href="https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)">Inversion</a>
%F A216239 a(n) = SUM(k=0..n-2, (-1)^k * n!/k! * (3*n+k)*(n-k-1) )/12. - _Max Alekseyev_, Aug 13 2013
%F A216239 a(n) = ( (3*n^2-n+1)*A000166(n) + (n-1)*(-1)^n )/12. - _Max Alekseyev_, Aug 14 2013
%F A216239 a(n) = Sum_{k>=1} A228924(n,k) * k. - _Alois P. Heinz_, Sep 22 2013
%F A216239 a(n) ~ n! * n^2 / (4*exp(1)). - _Vaclav Kotesovec_, Sep 10 2014
%e A216239 a(2) = 1: (2,1) has 1 inversion.
%e A216239 a(3) = 4: (2,3,1), (3,1,2) have 2+2 = 4 inversions.
%e A216239 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.
%p A216239 v:= proc(l) local i; for i to nops(l) do if l[i]=i then return 0 fi od;
%p A216239       add(add(`if`(l[i]>l[j], 1, 0), j=i+1..nops(l)), i=1..nops(l)-1)
%p A216239     end:
%p A216239 a:= n-> add(v(d), d=combinat[permute](n)):
%p A216239 seq(a(n), n=0..8);
%p A216239 # second Maple program:
%p A216239 a:= proc(n) option remember; `if`(n<3, n*(n-1)/2,
%p A216239       n*((6*n^3-26*n^2+31*n-9)*a(n-1)+(n-1)*
%p A216239       (6*n^2-8*n+1)*a(n-2))/((n-2)*(15-20*n+6*n^2)))
%p A216239     end:
%p A216239 seq(a(n), n=0..25);  # _Alois P. Heinz_, Aug 13 2013
%t A216239 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_ *)
%o A216239 (PARI) A216239(n) = sum(k=0,n-2, (-1)^k * n!/k! * (3*n+k) * (n-k-1) )/12; /* _Max Alekseyev_, Aug 13 2013 */
%Y A216239 Cf. A000166, A001809, A161124, A211606, A227404, A228924, A337193.
%K A216239 nonn
%O A216239 0,4
%A A216239 _Alois P. Heinz_, Mar 15 2013
%E A216239 Formula and terms a(15) onward from _Max Alekseyev_, Aug 13 2013