%I #28 Dec 10 2024 11:33:06
%S 1,1,1,3,5,13,37,107,341,1141,4021,14831,57017,227617,941305,4020455,
%T 17705753,80215513,373370329,1782362219,8716939229,43615569829,
%U 223069903933,1164867074483,6206075782925,33702629832685,186436337623597,1049745170246327,6012759489160241
%N Number of irreducible involutions of length n.
%C An involution x is irreducible if x(i+1) - x(i) <> 1 for all i < n. - _Andrew Howroyd_, May 06 2023
%H Andrew Howroyd, <a href="/A278024/b278024.txt">Table of n, a(n) for n = 0..500</a>
%H Jean-Luc Baril, <a href="https://hal.science/hal-01352852v1">Avoiding patterns in irreducible permutations</a>, Discrete Mathematics and Theoretical Computer Science, Vol. 17, No. 3 (2016). See Table 4.
%H Marilena Barnabei, Niccolò Castronuovo, and Matteo Silimbani, <a href="https://arxiv.org/abs/2412.03449">Hertzsprung patterns on involutions</a>, arXiv:2412.03449 [math.CO], 2024. See p. 10.
%F a(n) = Sum_{k=floor((n+2)/4)..floor(n/2)} Sum_{j=0..k} (-1)^(k-j) * binomial(k-1,k-j) * binomial(2*j+1,n-2*k) * (2*j)! / (2^j*j!). - _Andrew Howroyd_, May 08 2023
%e The a(3) = 3 irreducible involutions are: 132, 213, 321.
%e The a(4) = 5 irreducible involutions are: 1324, 1432, 2143, 3214, 4321.
%p a:= proc(n) option remember; `if`(n<7, [1$3, 3, 5, 13, 37][n+1],
%p (n-7)*a(n-7)+3*(n-6)*a(n-6)+4*(n-5)*a(n-5)
%p +(4*n-13)*a(n-4)+3*(n-3)*a(n-3)+(n-2)*a(n-2)-2*a(n-1))
%p end:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, May 08 2023
%o (PARI) a(n)=sum(k=(n+2)\4, n\2, sum(j=0, k, (-1)^(k-j)*binomial(k-1,k-j)*binomial(2*j+1,n-2*k)*(2*j)!/(2^j*j!))) \\ _Andrew Howroyd_, May 08 2023
%Y Cf. A000085, A244522, A278025.
%K nonn
%O 0,4
%A _N. J. A. Sloane_, Nov 09 2016
%E a(0)-a(1) and a(10)-a(12) from _Andrew Howroyd_, May 06 2023
%E a(13)-a(18) from _Joerg Arndt_, May 08 2023
%E Terms a(19) and beyond from _Andrew Howroyd_, May 08 2023