login
A260696
The number of length-n permutations avoiding the patterns 1234, 1324, 1432 and 3214.
0
1, 1, 2, 6, 20, 62, 172, 471, 1337, 3846, 11030, 31442, 89470, 254934, 727203, 2074435, 5915652, 16866988, 48093810, 137141828, 391072846, 1115164897, 3179915535, 9067592160, 25856510664, 73730732368, 210245631360, 599521974384, 1709555338705, 4874850377793, 13900789573274, 39638539791222
OFFSET
0,3
LINKS
C. Bean, M. Tannock and H. Ulfarsson, Pattern avoiding permutations and independent sets in graphs, arXiv:1512.08155 [math.CO], 2015.
FORMULA
G.f.: -(x^3 + x^2 + x - 1)/(7*x^9 + 14*x^8 + 15*x^7 - 8*x^5 - 4*x^4 - 2*x^3 - x^2 - 2*x + 1).
a(n) = 2*a(n-1)+a(n-2)+2*a(n-3)+4*a(n-4)+8*a(n-5)-15*a(n-7)-14*a(n-8)-7*a(n-9) for n>8. - Wesley Ivan Hurt, Dec 29 2015
MATHEMATICA
CoefficientList[Series[-(x^3 + x^2 + x - 1)/(7*x^9 + 14*x^8 + 15*x^7 - 8*x^5 - 4*x^4 - 2*x^3 - x^2 - 2*x + 1), {x, 0, 30}], x] (* Wesley Ivan Hurt, Dec 29 2015 *)
LinearRecurrence[{2, 1, 2, 4, 8, 0, -15, -14, -7}, {1, 1, 2, 6, 20, 62, 172, 471, 1337}, 40 ] (* Vincenzo Librandi, Dec 31 2015 *)
PROG
(Magma) I:=[1, 1, 2, 6, 20, 62, 172, 471, 1337]; [n le 9 select I[n] else 2*Self(n-1)+Self(n-2)+2*Self(n-3)+4*Self(n-4)+8*Self(n-5)-15*Self(n-7)-14*Self(n-8)-7*Self(n-9): n in [1..35]]; // Vincenzo Librandi, Dec 31 2015
CROSSREFS
Cf. A263790.
Sequence in context: A057766 A132353 A263900 * A052958 A247076 A177792
KEYWORD
nonn
AUTHOR
Christian Bean, Nov 26 2015
STATUS
approved