A114210 Number of derangements of [n] avoiding the patterns 123 and 231.

0, 1, 1, 3, 4, 7, 8, 14, 13, 23, 20, 34, 28, 48, 37, 64, 48, 82, 60, 103, 73, 126, 88, 151, 104, 179, 121, 209, 140, 241, 160, 276, 181, 313, 204, 352, 228, 394, 253, 438, 280, 484, 308, 533, 337, 584, 368, 637, 400, 693, 433, 751, 468, 811, 504, 874, 541, 939

Offset: 1

Author

Emeric Deutsch, Nov 17 2005

Keywords

• nonn
• easy

Examples

			a(2)=1 because we have 21; a(3)=1 because we have 312; a(4)=3 because we have 2143, 4312 and 4321.
		

Links

• T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, Annals of Combinatorics, 6, 2002, 407-418.
• Index entries for linear recurrences with constant coefficients, signature (-1,2,3,0,-3,-2,1,1).

Crossrefs

Cf. A114208, A114209.

Programs

Maple

a:=proc(n) if n mod 6 = 0 then (7*n^2-18*n+24)/24 elif n mod 6 = 1 or n mod 6 = 5 then (n^2-1)/6 elif n mod 6 = 2 or n mod 6 = 4 then (7*n^2-18*n+32)/24 else (n^2-3)/6 fi end: seq(a(n),n=1..70);

Mathematica

LinearRecurrence[{-1,2,3,0,-3,-2,1,1},{0,1,1,3,4,7,8,14},60] (* Harvey P. Dale, Mar 04 2023 *)

PARI

Vec(-x^2*(x^6+x^5+2*x^4+2*x^3+2*x^2+2*x+1)/((x-1)^3*(x+1)^3*(x^2+x+1)) + O(x^100)) \\ Colin Barker, Aug 14 2013

Formula

a(n) = binomial(n,2) + 1 - A114208(n) - A114209(n)

a(n) = (7n^2-18n+24)/24 if n mod 6 = 0; (n^2-1)/6 if n mod 6 = 1 or 5; (7n^2-18n+32)/24 if n mod 6 = 2 or 4; (n^2-3)/6 if n mod 6 = 3.

G.f.: -x^2*(x^6+x^5+2*x^4+2*x^3+2*x^2+2*x+1) / ((x-1)^3*(x+1)^3*(x^2+x+1)). - Colin Barker, Aug 14 2013