OFFSET
0,4
COMMENTS
An involution x is irreducible if x(i+1) - x(i) <> 1 for all i < n. - Andrew Howroyd, May 06 2023
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..500
J.-L. Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.
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
EXAMPLE
The a(3) = 3 irreducible involutions are: 132, 213, 321.
The a(4) = 5 irreducible involutions are: 1324, 1432, 2143, 3214, 4321.
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
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Nov 09 2016
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
STATUS
approved