|
|
A165534
|
|
Number of permutations of length n that avoid the patterns 1243 and 2431.
|
|
5
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
These permutations have an enumeration scheme of depth 5.
|
|
LINKS
|
|
|
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
|
|
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|