login
Number of permutations of length n which avoid the patterns 123, 3142, 4312; or avoid the patterns 123, 3421, 4231.
2

%I #13 Oct 24 2017 09:41:06

%S 1,2,5,12,24,42,67,100,142,194,257,332,420,522,639,772,922,1090,1277,

%T 1484,1712,1962,2235,2532,2854,3202,3577,3980,4412,4874,5367,5892,

%U 6450,7042,7669,8332,9032,9770,10547,11364,12222,13122,14065,15052,16084,17162

%N Number of permutations of length n which avoid the patterns 123, 3142, 4312; or avoid the patterns 123, 3421, 4231.

%H Colin Barker, <a href="/A116721/b116721.txt">Table of n, a(n) for n = 1..1000</a>

%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/maple/webbook/bookmain.html">Systematic Studies in Pattern Avoidance</a>, 2005.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-6,4,-1).

%F G.f.: x*(1 - 2*x + 3*x^2 - x^4) / (1 - x)^4.

%F For n >= 2, a(n) = (n^3 + 3n^2 - 16n + 24)/6. - _Franklin T. Adams-Watters_, Sep 16 2006

%F a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4) for n>5. - _Colin Barker_, Oct 24 2017

%p A116721 := proc(n) coeftayl(-x*(x^4-3*x^2+2*x-1)/(x-1)^4,x=0,n) ; end: seq(A116721(n),n=1..60) ; # _R. J. Mathar_, Jan 23 2008

%o (PARI) Vec(x*(1 - 2*x + 3*x^2 - x^4) / (1 - x)^4 + O(x^100)) \\ _Colin Barker_, Oct 24 2017

%K nonn,easy

%O 1,2

%A _Lara Pudwell_, Feb 26 2006

%E More terms from _R. J. Mathar_, Jan 23 2008