login
A278024
Number of irreducible involutions of length n.
2
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,4
COMMENTS
An involution x is irreducible if x(i+1) - x(i) <> 1 for all i < n. - Andrew Howroyd, May 06 2023
LINKS
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