A060696 Number of permutations in S_n avoiding the strings 123, 321 and 231.

1, 1, 2, 3, 5, 11, 23, 63, 153, 489, 1329, 4785, 14235, 56475, 181215, 780255, 2672145, 12348945, 44781345, 220253985, 840523635, 4370620275, 17465201775, 95498916975, 397983749625, 2278224696825, 9867844134225, 58917607974225

Offset: 0

Author

Tuwani A. Tshifhumulo (tat(AT)univen.ac.za), Apr 20 2001

Keywords

• nonn

Examples

			a(5) = (5-1)!! + (5-2)!! = 4!! + 3!! = 2*4 + 1*3 = 11.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..800
• S. Kitaev, Multi-avoidance of generalized patterns, Discrete Math., 260 (2003), 89-100.

Crossrefs

Cf. A011782.

Programs

Mathematica

Join[{1, 1}, Table[(n - 1)!! + (n - 2)!! , {n,2,50}]] (* G. C. Greubel, May 23 2017 *)

Formula

a(0)=1, a(1)=1, a(2)=2, a(3)=3, a(n) = (n-2)a(n-2)+(n-3)!! for n >= 4

E.g.f. for A(n)=a(n+1) (n>=0): (1+x)*exp(x^2/2)*(1+sqrt(Pi/2)*erf(x/sqrt(2))), where erf denotes the error function. - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Nov 01 2002

a(n) = (n-1)!!+(n-2)!! (cf. A006882).

Extensions

Corrected and extended by Vladeta Jovovic, Apr 22 2001