|
|
A211606
|
|
Total number of inversions over all involutions of length n.
|
|
7
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
REFERENCES
|
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 339.
|
|
LINKS
|
|
|
FORMULA
|
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:
|
|
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
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|