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