A165535 Number of permutations of length n which avoid the patterns 4231 and 3124.

1, 1, 2, 6, 22, 88, 363, 1508, 6255, 25842, 106327, 435965, 1782733, 7275351, 29648647, 120707058, 491113791, 1997372920, 8121565606, 33020039047, 134248625367, 545835561195, 2219474787024, 9025797884775, 36709145207578, 149320519008554, 607466672855393

Offset

0,3

References

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.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

M. H. Albert, M. D. Atkinson, and V. Vatter, Inflations of geometric grid classes: three case studies.

Wikipedia, Permutation classes avoiding two patterns of length 4.

Formula

G.f.: 1+(1-8*x+20*x^2-20*x^3+10*x^4-2*x^5-(1-4*x+2*x^2)*sqrt(1-4*x)) / (2*(1-3*x+x^2)*(-1+5*x-4*x^2+x^3)).

Example

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

Mathematica

CoefficientList[Series[1+(1-8*x+20*x^2-20*x^3+10*x^4-2*x^5-(1-4*x+ 2*x^2 )*Sqrt[1-4*x])/(2*(1-3*x+x^2)*(-1+5*x-4*x^2+x^3)), {x, 0, 30}], x] (* G. C. Greubel, Oct 22 2018 *)

Prog

(PARI) x='x+O('x^30); Vec(1+(1-8*x+20*x^2-20*x^3+10*x^4-2*x^5-(1-4*x +2*x^2)*sqrt(1-4*x))/(2*(1-3*x+x^2)*(-1+5*x-4*x^2+x^3))) \\ G. C. Greubel, Oct 22 2018
(Magma) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); Coefficients(R!(1+(1-8*x+20*x^2-20*x^3+10*x^4-2*x^5-(1-4*x+2*x^2)*Sqrt(1-4*x)) / (2*(1-3*x+x^2)*(-1+5*x-4*x^2+x^3)))); // G. C. Greubel, Oct 22 2018

Crossrefs

Sequence in context: A363811 A150263 A165534 * A319028 A165536 A032351

Adjacent sequences: A165532 A165533 A165534 * A165536 A165537 A165538

Keyword

nonn,easy

Author

Vincent Vatter, Sep 21 2009

Extensions

More terms, g.f., and reference by Vincent Vatter, Sep 04 2012

a(0)=1 prepended by Alois P. Heinz, Feb 18 2016

Status

approved