login
Number of permutations of length n which avoid the patterns 321, 1342, 3124.
0

%I #19 Jan 11 2024 10:11:44

%S 1,1,2,5,12,22,37,60,96,153,244,390,625,1004,1616,2605,4204,6790,

%T 10973,17740,28688,46401,75060,121430,196457,317852,514272,832085,

%U 1346316,2178358,3524629,5702940,9227520,14930409,24157876,39088230,63246049,102334220

%N Number of permutations of length n which avoid the patterns 321, 1342, 3124.

%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 (3, -2, -1, 1).

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

%F a(0)=1, a(1)=1, a(2)=2, a(3)=5, a(4)=12, a(5)=22, a(6)=37, a(n)=3*a(n-1)- 2*a(n-2)- a(n-3)+a (n-4). - _Harvey P. Dale_, Oct 21 2011

%F a(n) = F(n+3) + 2*n - 9 for n>2, where F is A000045. - _Jason Kimberley_, Nov 22 2013

%F For n>2, a(n) = (1+2/sqrt(5))*((1+sqrt(5))/2)^n + (1-2/sqrt(5))*((1-sqrt(5))/2)^n + 2*n - 9. - _Vaclav Kotesovec_, Dec 11 2013

%t Rest[CoefficientList[Series[1+((x+1)(2x^4+x^3-3x^2+2x-1)x)/((x-1)^2 (x^2+ x-1)),{x,0,50}],x]] (* or *) Join[{1,1,2},LinearRecurrence[{3,-2,-1,1},{5,12,22,37},50]] (* _Harvey P. Dale_, Oct 21 2011 *)

%K nonn,easy

%O 0,3

%A _Lara Pudwell_, Feb 26 2006