A211606 Total number of inversions over all involutions of length n.

0, 0, 1, 5, 26, 110, 490, 2086, 9240, 40776, 185820, 855580, 4048616, 19455800, 95773496, 479581480, 2454041920, 12776826816, 67849286160, 366455145936, 2015621873440, 11268605368160, 64074235576736, 370040657037920, 2171138049287296, 12928631894588800, 78139702237771200

Offset: 0

Author

Geoffrey Critzer, Feb 10 2013

Keywords

• nonn

Examples

			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.
		

References

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..800

Crossrefs

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

Programs

Maple

a:= proc(n) option remember; `if`(n<3, n*(n-1)/2,
      n*((n-2)*(9*n-7) *a(n-1) +(n-1)*(9*n^2-13*n+2) *a(n-2))/
      ((n-2)*(9*n^2-31*n+24)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Feb 12 2013

Mathematica

(* first do *) Needs["Combinatorica`"] // Quiet (* then *)
Table[Total[Map[Inversions, Involutions[n]]], {n, 0, 10}]
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 *)

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 */

Formula

From Alois P. Heinz, Feb 12 2013: (Start)

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

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.

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

(End)

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

Extensions

a(13)-a(15) from Alois P. Heinz, Feb 10 2013

Further terms from Alois P. Heinz, Feb 12 2013