A165530 - OEIS

%I #22 Sep 08 2022 08:45:48

%S 1,1,2,6,22,86,338,1314,5046,19190,72482,272530,1021734,3823622,

%T 14293234,53394370,199382550,744348822,2778471490,10370520178,

%U 38705706374,144456761766,539130777874,2012086272674,7509256255862,28025026831158,104591035618146

%N Number of permutations of length n which avoid the patterns 4321 and 3142.

%H Colin Barker, <a href="/A165530/b165530.txt">Table of n, a(n) for n = 0..1000</a>

%H Darla Kremer and Wai Chee Shiu, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00042-6">Finite transition matrices for permutations avoiding pairs of length four patterns</a>, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.

%H V. Vatter, <a href="https://arxiv.org/abs/0911.2683">Finding regular insertion encodings for permutation classes</a>, arXiv:0911.2683 [math.CO], 2009.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes#Classes_avoiding_two_patterns_of_length_4">Permutation classes avoiding two patterns of length 4</a>.

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

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

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

%F a(n) = (1/18)*(2*(3*2^n - (-3+sqrt(3))*(2+sqrt(3))^n + (2-sqrt(3))^n*(3+sqrt(3))) - 3*2^n*n).

%F a(n) = 8*a(n-1) - 21*a(n-2) + 20*a(n-3) - 4*a(n-4) for n>3.

%F (End)

%e There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.

%t CoefficientList[Series[(1-x)*(1-3*x)^2/((1-2*x)^2*(1-4*x+x^2)), {x, 0, 50}], x] (* _G. C. Greubel_, Oct 22 2018 *)

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

%o (Magma) m:=50; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x)*(1-3*x)^2/((1-2*x)^2*(1-4*x+x^2)))); // _G. C. Greubel_, Oct 22 2018

%K nonn,easy

%O 0,3

%A _Vincent Vatter_, Sep 21 2009

%E a(0)=1 prepended by _Alois P. Heinz_, Dec 09 2015