cp's OEIS Frontend

A211606 Total number of inversions over all involutions of length n.

%I A211606 #47 Aug 30 2020 13:00:32
%S A211606 0,0,1,5,26,110,490,2086,9240,40776,185820,855580,4048616,19455800,
%T A211606 95773496,479581480,2454041920,12776826816,67849286160,366455145936,
%U A211606 2015621873440,11268605368160,64074235576736,370040657037920,2171138049287296,12928631894588800,78139702237771200
%N A211606 Total number of inversions over all involutions of length n.
%D A211606 R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 339.
%H A211606 Alois P. Heinz, <a href="/A211606/b211606.txt">Table of n, a(n) for n = 0..800</a>
%F A211606 From _Alois P. Heinz_, Feb 12 2013: (Start)
%F A211606 a(n) = a(n-1) + (n-1)*a(n-2) + A000085(n-2)*(n-1)^2 for n>1; a(0) = a(1) = 0.
%F A211606 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.
%F A211606 E.g.f.: (x^2/2 + x^3/3 + x^4/4) * exp(x + x^2/2).
%F A211606 (End)
%F A211606 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
%e A211606 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.
%p A211606 a:= proc(n) option remember; `if`(n<3, n*(n-1)/2,
%p A211606       n*((n-2)*(9*n-7) *a(n-1) +(n-1)*(9*n^2-13*n+2) *a(n-2))/
%p A211606       ((n-2)*(9*n^2-31*n+24)))
%p A211606     end:
%p A211606 seq(a(n), n=0..30);  # _Alois P. Heinz_, Feb 12 2013
%t A211606 (* first do *) Needs["Combinatorica`"] // Quiet (* then *)
%t A211606 Table[Total[Map[Inversions, Involutions[n]]], {n, 0, 10}]
%t A211606 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 *)
%o A211606 (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 */
%Y A211606 Cf. A000085, A001809, A161124, A216239, A337193.
%K A211606 nonn
%O A211606 0,4
%A A211606 _Geoffrey Critzer_, Feb 10 2013
%E A211606 a(13)-a(15) from _Alois P. Heinz_, Feb 10 2013
%E A211606 Further terms from _Alois P. Heinz_, Feb 12 2013