|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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:
|
|
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
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|