A278024 Number of irreducible involutions of length n.

1, 1, 1, 3, 5, 13, 37, 107, 341, 1141, 4021, 14831, 57017, 227617, 941305, 4020455, 17705753, 80215513, 373370329, 1782362219, 8716939229, 43615569829, 223069903933, 1164867074483, 6206075782925, 33702629832685, 186436337623597, 1049745170246327, 6012759489160241

Offset: 0

Author

N. J. A. Sloane, Nov 09 2016

Keywords

• nonn

Comments

An involution x is irreducible if x(i+1) - x(i) <> 1 for all i < n. - Andrew Howroyd, May 06 2023

Examples

			The a(3) = 3 irreducible involutions are: 132, 213, 321.
The a(4) = 5 irreducible involutions are: 1324, 1432, 2143, 3214, 4321.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..500
• Jean-Luc Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol. 17, No. 3 (2016). See Table 4.
• Marilena Barnabei, Niccolò Castronuovo, and Matteo Silimbani, Hertzsprung patterns on involutions, arXiv:2412.03449 [math.CO], 2024. See p. 10.

Crossrefs

Cf. A000085, A244522, A278025.

Programs

Maple

a:= proc(n) option remember; `if`(n<7, [1$3, 3, 5, 13, 37][n+1],
      (n-7)*a(n-7)+3*(n-6)*a(n-6)+4*(n-5)*a(n-5)
     +(4*n-13)*a(n-4)+3*(n-3)*a(n-3)+(n-2)*a(n-2)-2*a(n-1))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, May 08 2023

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

Formula

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

Extensions

a(0)-a(1) and a(10)-a(12) from Andrew Howroyd, May 06 2023

a(13)-a(18) from Joerg Arndt, May 08 2023

Terms a(19) and beyond from Andrew Howroyd, May 08 2023