A278025 Number of irreducible involutions of length n avoiding the pattern {123}.

1, 3, 4, 9, 16, 31, 58, 112, 211, 411, 781, 1526, 2923, 5721, 11023, 21610, 41821, 82112, 159460, 313503, 610531, 1201721, 2345734, 4621899, 9039472, 17827054, 34923997, 68930585, 135231649, 267104311, 524673184, 1036989265, 2039191564, 4032728190, 7937870407

Offset: 1

Author

N. J. A. Sloane, Nov 09 2016

Keywords

• nonn

Links

• Robert Israel, Table of n, a(n) for n = 1..3323
• J.-L. Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.

Crossrefs

Cf. A278024.

Programs

Maple

f:= gfun:-rectoproc({(20 + 4*n)*a(n) + (-54 - 8*n)*a(1 + n) + (25 + 3*n)*a(n + 2) + (64 + 6*n)*a(n + 3) + (11 + 3*n)*a(n + 4) + (-67 - 9*n)*a(n + 5) + (45 + 7*n)*a(n + 6) + (10 - 2*n)*a(n + 7) + (2*n + 16)*a(n + 8) + (51 + 5*n)*a(n + 9) + (-9 - n)*a(n + 10) + (-13 - n)*a(n + 11), a(0) = 0, a(1) = 1, a(2) = 3, a(3) = 4, a(4) = 9, a(5) = 16, a(6) = 31, a(7) = 58, a(8) = 112, a(9) = 211, a(10) = 411, a(11) = 781},a(n),remember):
map(f, [$1..50]); # Robert Israel, Jul 23 2020

Formula

G.f.: ((1 + 2*x)*sqrt(1 - 4*x^2) - 1 + 4*x^2 - 2*x^3 + 2*x^4 + 4*x^5 )/((1 - 2*x)*(2*x^4 + 1 + sqrt(1 - 4*x^2))). - From Baril, corrected by Robert Israel, Jul 23 2020.

Extensions

More terms from Lars Blomberg, Nov 11 2016