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,4

Links

Table of n, a(n) for n=1..58.

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).

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

Example

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

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 *)

Prog

(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

Crossrefs

Cf. A114208, A114209.

Sequence in context: A345531 A357644 A120355 * A073271 A117471 A217135

Adjacent sequences: A114207 A114208 A114209 * A114211 A114212 A114213

Keyword

nonn,easy

Author

Emeric Deutsch, Nov 17 2005

Status

approved