login
This site is supported by donations to The OEIS Foundation.

 

Logo


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.

License Agreements, Terms of Use, Privacy Policy. .

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