A165524 Number of permutations of length n which avoid the patterns 4321 and 1324.

1, 2, 6, 22, 86, 332, 1217, 4140, 12934, 37088, 98115, 241269, 555881, 1208988, 2498732, 4936275, 9367783, 17151454, 30408684, 52373368, 87869112, 143950884, 230755459, 362614022, 559490596, 848821676, 1267845697, 1866525871, 2711186627, 3889002516, 5513499142

Offset

1,2

Links

T. D. Noe, Table of n, a(n) for n = 1..1000

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.

V. Vatter, Finding regular insertion encodings for permutation classes, Journal of Symbolic Computation, Volume 47, Issue 3, March 2012, Pages 259-265.

Wikipedia, Permutation classes avoiding two patterns of length 4

Index entries for linear recurrences with constant coefficients, signature (12,-66,220,-495,792,-924,792,-495,220,-66,12,-1).

Formula

G.f.: (1-11*x-413*x^7+217*x^8+554*x^6-2*x^11+357*x^4 -83*x^9-519*x^5 +20*x^10 +56*x^2-172*x^3) / (1-x)^12.

a(n) = 12*a(n-1) - 66*a(n-2) + 220*a(n-3) - 495*a(n-4) + 792*a(n-5) - 924*a(n-6) + 792*a(n-7) - 495*a(n-8) + 220*a(n-9) - 66*a(n-10) + 12*a(n-11) - a(n-12) for n>12. - Colin Barker, Oct 31 2017

Example

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

Mathematica

CoefficientList[Series[(1-11*x-413*x^7+217*x^8+554*x^6-2*x^11+357*x^4 -83*x^9-519*x^5 +20*x^10 +56*x^2-172*x^3)/(1-x)^12, {x, 0, 50}], x] (* G. C. Greubel, Oct 21 2018 *)
LinearRecurrence[{12, -66, 220, -495, 792, -924, 792, -495, 220, -66, 12, -1}, {1, 2, 6, 22, 86, 332, 1217, 4140, 12934, 37088, 98115, 241269}, 40] (* Harvey P. Dale, Jan 03 2019 *)

Prog

(PARI) Vec(x*(1 - 10*x + 48*x^2 - 138*x^3 + 273*x^4 - 370*x^5 + 379*x^6 - 278*x^7 + 137*x^8 - 46*x^9 + 10*x^10 - x^11) / (1 - x)^12 + O(x^40)) \\ Colin Barker, Oct 31 2017
(Magma) m:=50; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-11*x-413*x^7+217*x^8+554*x^6-2*x^11+357*x^4 -83*x^9-519*x^5 +20*x^10 +56*x^2-172*x^3)/(1-x)^12)); // G. C. Greubel, Oct 21 2018

Crossrefs

Sequence in context: A116705 A116708 A116706 * A165525 A165526 A165527

Adjacent sequences: A165521 A165522 A165523 * A165525 A165526 A165527

Keyword

nonn,easy

Author

Vincent Vatter, Sep 21 2009

Status

approved