login
A165537
Number of permutations of length n which avoid the patterns 4213 and 2143.
1
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.
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
a(n) ~ 12 * 5^(n + 3/2) / (121 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jul 07 2024
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
KEYWORD
nonn
AUTHOR
Vincent Vatter, Sep 21 2009
EXTENSIONS
More terms from David Bevan, Sep 25 2015
STATUS
approved