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
Keywords
Examples
There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.
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.
Crossrefs
The simple permutations in this class are given by A226430.
Programs
-
Magma
m:=30; R
:=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 -
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 *) -
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
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
Extensions
More terms from Jay Pantone, Sep 08 2013
Comments