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,4

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

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

Example

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.

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

Prog

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

Crossrefs

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

Sequence in context: A297689 A002316 A293799 * A005499 A185552 A171702

Adjacent sequences: A211603 A211604 A211605 * A211607 A211608 A211609

Keyword

nonn

Author

Geoffrey Critzer, Feb 10 2013

Extensions

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

Further terms from Alois P. Heinz, Feb 12 2013

Status

approved