login
Number of permutations of length n that avoid the patterns 321, 1342, 4123.
1

%I #22 Jan 19 2024 09:53:00

%S 1,1,2,5,12,24,46,87,162,300,554,1021,1880,3460,6366,11711,21542,

%T 39624,72882,134053,246564,453504,834126,1534199,2821834,5190164,

%U 9546202,17558205,32294576,59398988,109251774,200945343,369596110,679793232,1250334690,2299724037

%N Number of permutations of length n that avoid the patterns 321, 1342, 4123.

%H Paolo Xausa, <a href="/A116714/b116714.txt">Table of n, a(n) for n = 0..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 (2,0,0,-1).

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

%p A116714 := proc(n)

%p if n = 1 then

%p 1;

%p else

%p -5+A000073(n+2)+4*A000073(n+1)+3*A000073(n) ;

%p %/2 ;

%p end if;

%p end proc:

%p seq(A116714(n),n=1..20) ; # _R. J. Mathar_, Jan 11 2024

%t LinearRecurrence[{2, 0, 0, -1}, {1, 1, 2, 5, 12, 24}, 50] (* _Paolo Xausa_, Jan 19 2024 *)

%K nonn,easy

%O 0,3

%A _Lara Pudwell_, Feb 26 2006

%E a(0)=1 prepended by _Alois P. Heinz_, Jan 19 2024