A165527 Number of permutations of length n which avoid the patterns 4231 and 2143.

1, 2, 6, 22, 86, 335, 1271, 4680, 16766, 58656, 201106, 677767, 2251011, 7382992, 23955716, 77010180, 245577076, 777648145, 2447486221, 7661760386, 23872087936, 74071120682, 228988898916, 705618033237, 2168073549821, 6644571015750, 20317533778906

Offset

1,2

References

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

Links

Colin Barker, Table of n, a(n) for n = 1..1000

M. H. Albert, M. D. Atkinson, and R. Brignall, The enumeration of permutations avoiding 2143 and 4231

Wikipedia, Permutation classes avoiding two patterns of length 4

Index entries for linear recurrences with constant coefficients, signature (13,-71,213,-386,438,-311,133,-31,3).

Formula

G.f.: (x-11*x^2+51*x^3-127*x^4+186*x^5-165*x^6+87*x^7-23*x^8+3*x^9) / ((1-3*x)*(1-x)^4*(1-3*x+x^2)^2). - Vincent Vatter, Jun 21 2011

Example

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

Mathematica

CoefficientList[Series[(x-11*x^2+51*x^3-127*x^4+186*x^5-165*x^6+87*x^7 -23*x^8+3*x^9)/((1-3*x)*(1-x)^4*(1-3*x+x^2)^2), {x, 0, 50}], x] (* G. C. Greubel, Oct 22 2018 *)

Prog

(PARI) Vec(x*(1 - 11*x + 51*x^2 - 127*x^3 + 186*x^4 - 165*x^5 + 87*x^6 - 23*x^7 + 3*x^8) / ((1 - x)^4*(1 - 3*x)*(1 - 3*x + x^2)^2) + O(x^30)) \\ Colin Barker, Oct 31 2017
(Magma) m:=50; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((x -11*x^2+51*x^3-127*x^4+186*x^5-165*x^6+87*x^7 -23*x^8+3*x^9)/((1-3*x)* (1-x)^4*(1-3*x+x^2)^2))); // G. C. Greubel, Oct 22 2018

Crossrefs

Sequence in context: A165524 A165525 A165526 * A165528 A116709 A165529

Adjacent sequences: A165524 A165525 A165526 * A165528 A165529 A165530

Keyword

nonn,easy

Author

Vincent Vatter, Sep 21 2009

Extensions

More terms from Vincent Vatter, Jun 21 2011

Status

approved