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

 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 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 Cf. A000085, A244522, A278025. Sequence in context: A306826 A175257 A190423 * A198636 A172023 A271667 Adjacent sequences: A278021 A278022 A278023 * A278025 A278026 A278027 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.

Last modified August 6 18:55 EDT 2024. Contains 374981 sequences. (Running on oeis4.)