This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A211606 Total number of inversions over all involutions of length n. 6
 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 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. 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 24 17:50 EDT 2019. Contains 324330 sequences. (Running on oeis4.)