A165537 Number of permutations of length n which avoid the patterns 4213 and 2143.

1, 2, 6, 22, 88, 366, 1556, 6720, 29396, 129996, 580276, 2611290, 11834116, 53963190, 247414100, 1139860150, 5274189156, 24498929370, 114199276476, 534028437710, 2504543749532, 11777411979050, 55518128412708, 262301674637860, 1241868060613788, 5891050888101112, 27995910970158108

Offset

1,2

Links

G. C. Greubel, Table of n, a(n) for n = 1..1000 (terms 1..100 from David Bevan)

David Bevan, The permutation class Av(4213,2143), arXiv:1510.06328 [math.CO], 2015.

Kremer, Darla and Shiu, Wai Chee, 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.

Formula

G.f.: ((1-2*z) * (-1 + 5*z - 7*z^2 + 2*z^3 + (1-z)*sqrt(1 - 6*z + 5*z^2))) / (1 - 10*z + 24*z^2 - 20*z^3 + 4*z^4). - David Bevan, Sep 25 2015

Conjecture: n*a(n) + 2*(-9*n+7)*a(n-1) + (121*n-204)*a(n-2) + 28*(-14*n+37)*a(n-3) + 16*(42*n-151)*a(n-4) + 4*(-153*n+694)*a(n-5) + 4*(67*n-364)*a(n-6) + 40*(-n+6)*a(n-7) = 0. - R. J. Mathar, Jun 14 2016

Example

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

Mathematica

Rest[CoefficientList[Series[((1-2*x)*(-1 +5*x -7*x^2 +2*x^3 +(1 - x)*Sqrt[1-6*x+5*x^2]))/(1-10*x+24*x^2-20*x^3+4*x^4), {x, 0, 50}], x]] (* G. C. Greubel, Oct 22 2018 *)

Prog

(PARI) z='z+O('z^66); Vec( ((1-2*z) * (-1 +5*z -7*z^2 +2*z^3 +(1-z) * sqrt(1 -6*z +5*z^2))) / (1 -10*z +24*z^2 -20*z^3 +4*z^4) ) \\ Joerg Arndt, Sep 27 2015
(Magma) m:=50; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!(((1-2*x)*(-1 +5*x -7*x^2 +2*x^3 +(1 - x)*Sqrt(1-6*x+5*x^2)))/(1-10*x +24*x^2-20*x^3+4*x^4))); // G. C. Greubel, Oct 22 2018

Crossrefs

Sequence in context: A319028 A165536 A032351 * A165538 A165539 A109033

Adjacent sequences: A165534 A165535 A165536 * A165538 A165539 A165540

Keyword

nonn

Author

Vincent Vatter, Sep 21 2009

Extensions

More terms from David Bevan, Sep 25 2015

Status

approved