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
KEYWORD
nonn,easy
AUTHOR
Emeric Deutsch, Nov 17 2005
STATUS
approved