A114215 Number of derangements of [n] avoiding the patterns 123, 132 and 213.

0, 1, 2, 4, 4, 9, 12, 25, 30, 64, 80, 169, 208, 441, 546, 1156, 1428, 3025, 3740, 7921, 9790, 20736, 25632, 54289, 67104, 142129, 175682, 372100, 459940, 974169, 1204140, 2550409, 3152478, 6677056, 8253296, 17480761, 21607408, 45765225

Offset

1,3

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, Annals of Combinatorics, 6, 2002, 407-418; Theorem 3.2.

Index entries for linear recurrences with constant coefficients, signature (0,2,0,2,0,-1).

Formula

a(n) = F(n)-F((n-2)/2)^2 if n is even; a(n)=F(n)-F((n-1)/2)^2 if n is odd; here F(n) is the Fibonacci sequence with F(0)=F(1)=1.

a(n) = 2*a(n-2)+2*a(n-4)-a(n-6). G.f.: -x^2*(x+1)*(x^3-x^2-x-1) / ((x^2-x-1)*(x^2+1)*(x^2+x-1)). - Colin Barker, Mar 29 2014

Example

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

Maple

with(combinat): F:=n->fibonacci(n+1): a:=proc(n) if n mod 2 = 0 then F(n)-F((n-2)/2)^2 else F(n)-F((n-1)/2)^2 fi end: seq(a(n), n=1..45);

Mathematica

CoefficientList[Series[- x (x + 1) (x^3 - x^2 - x - 1)/((x^2 - x - 1) (x^2 + 1) (x^2 + x - 1)), {x, 0, 50}], x] (* Vincenzo Librandi, Mar 29 2014 *)

Crossrefs

Cf. A007598 (bisection), A079472 (bisection).

Sequence in context: A335057 A039887 A216162 * A292302 A151712 A253827

Adjacent sequences: A114212 A114213 A114214 * A114216 A114217 A114218

Keyword

nonn,easy

Author

Emeric Deutsch, Nov 17 2005

Status

approved