|
%I #35 Sep 08 2022 08:45:48
%S 1,2,6,22,88,363,1507,6241,25721,105485,430767,1752945,7113095,
%T 28797292,116368938,469531170,1892133076,7617145998,30638026074,
%U 123145086046,494663313342,1985995240464,7969941119476,31971818819844,128214549263032,514024475597524,2060262910065740,8255954041620260
%N Number of permutations of length n that avoid the patterns 1243 and 2431.
%C These permutations have an enumeration scheme of depth 5.
%H Vincenzo Librandi, <a href="/A165534/b165534.txt">Table of n, a(n) for n = 1..1000</a>
%H Kremer, Darla and Shiu, Wai Chee; <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 Jay Pantone, <a href="http://arxiv.org/abs/1309.0832">The Enumeration of Permutations Avoiding 3124 and 4312</a>, arXiv:1309.0832 [math.CO], (2013)
%H V. Vatter, <a href="http://www.math.ufl.edu/~vatter/publications/wilfplus/">Enumeration schemes for restricted permutations</a>, Combin., Prob. and Comput. 17 (2008), 137-159.
%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>.
%F G.f.: -(8*x^4 - 7*x^3 + x^2 + sqrt(-4*x + 1)*(4*x^4 - 9*x^3 + 9*x^2 - 2*x))/(12*x^4 - 31*x^3 + 27*x^2 + sqrt(-4*x + 1)*(4*x^4 - 13*x^3 + 15*x^2 - 7*x + 1) - 9*x + 1). - _Jay Pantone_, Sep 08 2013
%F Recurrence (for n>5): (n-5)*(n+2)*(n^3 - 69*n^2 + 434*n - 756)*a(n) = 2*(5*n^5 - 363*n^4 + 3509*n^3 - 11217*n^2 + 8006*n + 11760)*a(n-1) - 3*(11*n^5 - 804*n^4 + 8357*n^3 - 32556*n^2 + 50672*n - 21000)*a(n-2) + 2*(20*n^5 - 1467*n^4 + 15806*n^3 - 66753*n^2 + 123854*n - 83160)*a(n-3) - 8*(n-4)*(2*n-7)*(n^3 - 66*n^2 + 299*n - 390)*a(n-4). - _Vaclav Kotesovec_, Sep 09 2013
%F a(n) ~ 4^n/9 * (1+1/sqrt(Pi*n)). - _Vaclav Kotesovec_, Sep 09 2013
%e There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.
%t CoefficientList[Series[-(1 / x) (8 x^4 - 7 x^3 + x^2 + Sqrt[-4 x + 1] (4 x^4 - 9 x^3 + 9 x^2 - 2 x)) / (12 x^4 - 31 x^3 + 27 x^2 + Sqrt[-4 x + 1] (4 x^4 - 13 x^3 + 15 x^2 - 7 x + 1) - 9 x + 1), {x, 0, 30}], x] (* _Vincenzo Librandi_, Sep 10 2013 *)
%o (PARI) x='x+O('x^30); Vec(-(8*x^4-7*x^3+x^2 +sqrt(-4*x+1)*(4*x^4 -9*x^3 +9*x^2-2*x))/(12*x^4-31*x^3+27*x^2 +sqrt(-4*x+1)*(4*x^4-13*x^3 +15*x^2 -7*x +1) -9*x +1)) \\ _G. C. Greubel_, Oct 22 2018
%o (Magma) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); Coefficients(R!(-(8*x^4 -7*x^3 +x^2 +Sqrt(-4*x+1)*(4*x^4 -9*x^3 +9*x^2 -2*x))/(12*x^4 - 31*x^3+27*x^2 +Sqrt(-4*x+1)*(4*x^4-13*x^3+15*x^2-7*x+1) -9*x +1))); // _G. C. Greubel_, Oct 22 2018
%Y The simple permutations in this class are given by A226430.
%K nonn
%O 1,2
%A _Vincent Vatter_, Sep 21 2009
%E More terms from _Jay Pantone_, Sep 08 2013
| 