A116713 - OEIS

%I #13 Oct 19 2017 14:25:16

%S 1,2,5,12,24,45,83,154,290,555,1077,2112,4172,8281,16487,32886,65670,

%T 131223,262313,524476,1048784,2097381,4194555,8388882,16777514,

%U 33554755,67109213,134218104,268435860,536871345,1073742287,2147484142,4294967822,8589935151

%N Number of permutations of length n which avoid the patterns 123, 2431, 4132.

%H Colin Barker, <a href="/A116713/b116713.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 (5,-9,7,-2).

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

%F From _Colin Barker_, Oct 19 2017: (Start)

%F a(n) = (-4 + 2^n - n + n^2) / 2 for n>2.

%F a(n) = 5*a(n-1) - 9*a(n-2) + 7*a(n-3) - 2*a(n-4) for n>6.

%F (End)

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

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

%K nonn,easy

%O 1,2

%A _Lara Pudwell_, Feb 26 2006