A165526 Number of permutations of length n which avoid the patterns 4312 and 1324.

1, 1, 2, 6, 22, 86, 335, 1266, 4598, 16016, 53579, 172663, 537957, 1626504, 4789128, 13777002, 38833685, 107531833, 293178623, 788633906, 2096774922, 5519058020, 14402858655, 37314455547, 96088754649, 246213555740, 628392990988, 1598928688542, 4059458611305, 10291457844285

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), no. 1-3, 171-183. MR1983276 (2004b:05006). See Table 1.

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

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)

Wikipedia, Permutation classes avoiding two patterns of length 4

Index entries for linear recurrences with constant coefficients, signature (17,-128,561,-1581,2984,-3804, 3216,-1712,512,-64)

Formula

G.f.: (4*x^10 -127*x^9 +692*x^8 -1657*x^7 +2305*x^6 -2045*x^5 +1196*x^4 -461*x^3 +113*x^2 -16*x+1) / ((x-1)^2 *(2*x-1)^6 *(x^2-3*x+1)). - Colin Barker, Jul 05 2013

Example

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

Mathematica

CoefficientList[Series[(4*x^10 -127*x^9 +692*x^8 -1657*x^7 +2305*x^6 - 2045*x^5 +1196*x^4 -461*x^3 +113*x^2 -16*x +1)/((x-1)^2*(2*x-1)^6*(x^2 - 3*x +1)), {x, 0, 50}], x] (* G. C. Greubel, Oct 22 2018 *)

Prog

(PARI) x='x+O('x^50); Vec((4*x^10 -127*x^9 +692*x^8 -1657*x^7 +2305*x^6 - 2045*x^5 +1196*x^4 -461*x^3 +113*x^2 -16*x +1)/((x-1)^2*(2*x-1)^6*(x^2 - 3*x +1))) \\ G. C. Greubel, Oct 22 2018
(Magma) m:=50; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((4*x^10 -127*x^9 +692*x^8 -1657*x^7 +2305*x^6 - 2045*x^5 +1196*x^4 -461*x^3 +113*x^2 -16*x +1)/((x-1)^2*(2*x-1)^6*(x^2 - 3*x +1)))); // G. C. Greubel, Oct 22 2018

Crossrefs

Sequence in context: A116706 A165524 A165525 * A165527 A165528 A116709

Adjacent sequences: A165523 A165524 A165525 * A165527 A165528 A165529

Keyword

nonn,easy

Author

Vincent Vatter, Sep 21 2009

Status

approved