A165529 Number of permutations of length n which avoid the patterns 4312 and 2143.

1, 1, 2, 6, 22, 86, 337, 1295, 4854, 17760, 63594, 223488, 772841, 2635733, 8882042, 29622114, 97901974, 321016826, 1045294921, 3382803539, 10887874254, 34873641228, 111215129370, 353295398148, 1118381630705, 3529144183433, 11104719198770, 34851434248542, 109121784244342, 340934806542302

Offset

0,3

Links

Jay Pantone, Table of n, a(n) for n = 0..500

M. H. Albert, M. D. Atkinson, Robert Brignall, The enumeration of three pattern classes using monotone grid classes, The Electronic Journal of Combinatorics, vol.19, no.3, (2012)

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

Wikipedia, Permutation classes avoiding two patterns of length 4

Index entries for linear recurrences with constant coefficients, signature (17, -124, 507, -1275, 2040, -2083, 1331, -508, 105, -9).

Formula

G.f.: (1 - 2*x)*(1 - 14*x + 81*x^2 - 249*x^3 + 438*x^4 - 447*x^5 + 260*x^6 - 82*x^7 + 14*x^8)/((1 - x)^2*(1 - 3*x + x^2)^3*(1 - 3*x)^2). [corrects minor error in Albert et al., 2012] - Jay Pantone, Dec 05 2017

Example

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

Mathematica

CoefficientList[Series[(1 - 2 x) (1 - 14 x + 81 x^2 - 249 x^3 + 438 x^4 - 447 x^5 + 260 x^6 - 82 x^7 + 14 x^8)/((1 - x)^2*(1 - 3 x + x^2)^3*(1 - 3 x)^2), {x, 0, 29}], x] (* Michael De Vlieger, Dec 12 2017 *)

Prog

(PARI) x='x+O('x^50); Vec((1-2*x)*(1-14*x+81*x^2-249*x^3+438*x^4-447*x^5 + 260*x^6-82*x^7+14*x^8)/((1-x)^2*(1-3*x+x^2)^3*(1-3*x)^2)) \\ G. C. Greubel, Oct 22 2018
(Magma) m:=50; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((1 - 2*x)*(1-14*x+81*x^2-249*x^3+438*x^4-447*x^5+260*x^6-82*x^7+14*x^8)/((1 - x)^2*(1-3*x+x^2)^3*(1-3*x)^2))); // G. C. Greubel, Oct 22 2018

Crossrefs

Sequence in context: A165527 A165528 A116709 * A116710 A165530 A116707

Adjacent sequences: A165526 A165527 A165528 * A165530 A165531 A165532

Keyword

nonn

Author

Vincent Vatter, Sep 21 2009

Extensions

More terms from N. J. A. Sloane, Aug 22 2012

Corrected terms from Jay Pantone, Dec 05 2017

Status

approved