login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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
Sequence in context: A306826 A175257 A190423 * A198636 A172023 A271667
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 16:34 EDT 2024. Contains 371254 sequences. (Running on oeis4.)