A278024 Number of irreducible involutions of length n.
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
Keywords
Examples
The a(3) = 3 irreducible involutions are: 132, 213, 321. The a(4) = 5 irreducible involutions are: 1324, 1432, 2143, 3214, 4321.
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..500
- Jean-Luc Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol. 17, No. 3 (2016). See Table 4.
- Marilena Barnabei, Niccolò Castronuovo, and Matteo Silimbani, Hertzsprung patterns on involutions, arXiv:2412.03449 [math.CO], 2024. See p. 10.
Programs
-
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 -
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
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
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
Comments