A211606 - OEIS

%I #47 Aug 30 2020 13:00:32

%S 0,0,1,5,26,110,490,2086,9240,40776,185820,855580,4048616,19455800,

%T 95773496,479581480,2454041920,12776826816,67849286160,366455145936,

%U 2015621873440,11268605368160,64074235576736,370040657037920,2171138049287296,12928631894588800,78139702237771200

%N Total number of inversions over all involutions of length n.

%D R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 339.

%H Alois P. Heinz, <a href="/A211606/b211606.txt">Table of n, a(n) for n = 0..800</a>

%F From _Alois P. Heinz_, Feb 12 2013: (Start)

%F a(n) = a(n-1) + (n-1)*a(n-2) + A000085(n-2)*(n-1)^2 for n>1; a(0) = a(1) = 0.

%F a(n) = (n*(n-2)*(9*n-7) *a(n-1) +n*(n-1)*(9*n^2-13*n+2) *a(n-2))/ ((n-2)*(9*n^2-31*n+24)) for n>=3; a(n) = n*(n-1)/2 for n<3.

%F E.g.f.: (x^2/2 + x^3/3 + x^4/4) * exp(x + x^2/2).

%F (End)

%F a(n) ~ sqrt(2)/8 * n^(n/2+2)*exp(sqrt(n)-n/2-1/4) * (1-3/(8*sqrt(n))). - _Vaclav Kotesovec_, Aug 15 2013

%e a(3) = 5 because in the involutions of {1,2,3}: (given in word form) 213, 321, 132, 123, there are respectively 1 + 3 + 1 + 0 = 5 inversions.

%p a:= proc(n) option remember; `if`(n<3, n*(n-1)/2,

%p       n*((n-2)*(9*n-7) *a(n-1) +(n-1)*(9*n^2-13*n+2) *a(n-2))/

%p       ((n-2)*(9*n^2-31*n+24)))

%p     end:

%p seq(a(n), n=0..30);  # _Alois P. Heinz_, Feb 12 2013

%t (* first do *) Needs["Combinatorica`"] // Quiet (* then *)

%t Table[Total[Map[Inversions, Involutions[n]]], {n, 0, 10}]

%t a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ (x^2/2 + x^3/3 + x^4/4) Exp[x + x^2/2], {x, 0, n}]]; (* _Michael Somos_, Jun 03 2019 *)

%o (PARI) {a(n) = if( n<0, 0, n! * polcoeff( (x^2/2 + x^3/3 + x^4/4) * exp(x + x^2/2 + x * O(x^n)), n))}; /* _Michael Somos_, Jun 03 2019 */

%Y Cf. A000085, A001809, A161124, A216239, A337193.

%K nonn

%O 0,4

%A _Geoffrey Critzer_, Feb 10 2013

%E a(13)-a(15) from _Alois P. Heinz_, Feb 10 2013

%E Further terms from _Alois P. Heinz_, Feb 12 2013