|
%I #50 Dec 04 2023 12:32:32
%S 1,0,0,1,1,2,10,17,39,119,254,613,1623,3791,9281,23469,56823,140035,
%T 349167,857868,2122297,5274213,13044870,32357838,80421284,199613489,
%U 496144310,1234420850,3070773600,7644879181,19044266176,47450853932,118290412077,295019269801
%N Number of involutions of length n having exactly n inversions.
%H Alois P. Heinz, <a href="/A214086/b214086.txt">Table of n, a(n) for n = 0..2000</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)">Inversion</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Involution_(mathematics)">Involution</a>
%F a(n) = T(n,n) with T(n,k) = T(n-1,k) + Sum_{j=1..n-1} T(n-2,k-2*(n-j)+1) for n>=0, k>0; T(n,k) = 0 for n<0 or k<0; T(n,0) = 1 for n>=0.
%F a(n) ~ c * d^n / sqrt(n), where d = 2.529010713480526199368... is the root of the equation 4 - 23*d - 36*d^2 - 8*d^3 + 4*d^5 = 0, c = 0.08933570507578447270759... . - _Vaclav Kotesovec_, Sep 07 2014
%e a(0) = 1: (), the empty involution.
%e a(3) = 1: (3,2,1); inversions are (3,2), (3,1), (2,1).
%e a(4) = 1: (3,4,1,2); inversions are (3,1), (3,2), (4,1), (4,2).
%e a(5) = 2: (1,5,3,4,2), (4,2,3,1,5).
%e a(6) = 10: (1,2,6,5,4,3), (1,4,6,2,5,3), (1,5,3,6,2,4), (1,5,4,3,2,6), (2,1,6,4,5,3), (3,2,1,6,5,4), (3,5,1,4,2,6), (4,2,3,1,6,5), (4,2,5,1,3,6), (4,3,2,1,5,6).
%p T:= proc(n, k) option remember; `if`(n<0 or k<0, 0, `if`(k=0, 1,
%p T(n-1, k) + add(T(n-2, k-2*(n-j)+1), j=1..n-1)))
%p end:
%p a:= n-> T(n$2):
%p seq(a(n), n=0..50);
%t Needs["Combinatorica`"];
%t Table[Count[Map[Inversions,Involutions[n]],n],{n,0,12}]
%t (* Second program: *)
%t T[n_, k_] := T[n, k] = If[n < 0 || k < 0, 0, If[k == 0, 1, T[n-1, k] + Sum[T[n-2, k-2*(n-j)+1], {j, 1, n-1}]]];
%t a[n_] := T[n, n];
%t Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Dec 04 2023, after Maple code *)
%Y Diagonal of A213910.
%Y Cf. A128566.
%K nonn
%O 0,6
%A _Geoffrey Critzer_ and _Alois P. Heinz_, Mar 06 2013
|
