A165528 Number of permutations of length n which avoid the patterns 1324 and 4231.

1, 1, 2, 6, 22, 86, 336, 1282, 4758, 17234, 61242, 214594, 744594, 2566594, 8809442, 30157826, 103082050, 352045314, 1201795970, 4101913602, 13999868162, 47782800386, 163095158274, 556717514754, 1900427035650, 6487635578882, 22148113283074, 75613356769282

Offset

0,3

Links

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

M. Albert, M. Atkinson, and V. Vatter, Counting 1324-, 4231-avoiding permutations, The Electronic Journal of Combinatorics, Volume 16, Issue 1 (2009).

Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.

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.

Wikipedia, Permutation classes avoiding two patterns of length 4

Index entries for linear recurrences with constant coefficients, signature (13,-70,202,-336,320,-160,32).

Formula

G.f.: (1-12*x+59*x^2-152*x^3+218*x^4-168*x^5+58*x^6-6*x^7) / ((1-x) *(1-2*x)^4 *(1-4*x+2*x^2)).

Example

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

Mathematica

CoefficientList[Series[(1 -12*x +59*x^2 -152*x^3 +218*x^4 -168*x^5 + 58*x^6 -6*x^7)/((1-x)*(1-2*x)^4*(1-4*x+2*x^2)), {x, 0, 50}], x] (* G. C. Greubel, Oct 22 2018 *)

Prog

(PARI)
gf=(1-12*x+59*x^2-152*x^3+218*x^4-168*x^5+58*x^6-6*x^7)/( (1-x)*(1-2*x)^4*(1-4*x+2*x^2) )
v165528=Vec(gf+O('x^66))
/* Joerg Arndt, Aug 16 2012 */
(Magma) m:=50; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((1 -12*x +59*x^2 -152*x^3 +218*x^4 -168*x^5 + 58*x^6 -6*x^7)/((1-x)*(1- 2*x)^4*(1-4*x+2*x^2)))); // G. C. Greubel, Oct 22 2018

Crossrefs

Sequence in context: A165525 A165526 A165527 * A116709 A165529 A116710

Adjacent sequences: A165525 A165526 A165527 * A165529 A165530 A165531

Keyword

nonn

Author

Vincent Vatter, Sep 21 2009

Extensions

Prepended a(0)=1 by Joerg Arndt, Aug 16 2012

Status

approved