A165534 Number of permutations of length n that avoid the patterns 1243 and 2431.

1, 2, 6, 22, 88, 363, 1507, 6241, 25721, 105485, 430767, 1752945, 7113095, 28797292, 116368938, 469531170, 1892133076, 7617145998, 30638026074, 123145086046, 494663313342, 1985995240464, 7969941119476, 31971818819844, 128214549263032, 514024475597524, 2060262910065740, 8255954041620260

Offset

1,2

Comments

These permutations have an enumeration scheme of depth 5.

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Kremer, Darla and Shiu, Wai Chee; Finite transition matrices for permutations avoiding pairs of length four patterns. Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.

Jay Pantone, The Enumeration of Permutations Avoiding 3124 and 4312, arXiv:1309.0832 [math.CO], (2013)

V. Vatter, Enumeration schemes for restricted permutations, Combin., Prob. and Comput. 17 (2008), 137-159.

Wikipedia, Permutation classes avoiding two patterns of length 4.

Formula

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

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

a(n) ~ 4^n/9 * (1+1/sqrt(Pi*n)). - Vaclav Kotesovec, Sep 09 2013

Example

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

Mathematica

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 *)

Prog

(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
(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

Crossrefs

The simple permutations in this class are given by A226430.

Sequence in context: A101046 A363811 A150263 * A165535 A319028 A165536

Adjacent sequences: A165531 A165532 A165533 * A165535 A165536 A165537

Keyword

nonn

Author

Vincent Vatter, Sep 21 2009

Extensions

More terms from Jay Pantone, Sep 08 2013

Status

approved