login
A165530
Number of permutations of length n which avoid the patterns 4321 and 3142.
2
1, 1, 2, 6, 22, 86, 338, 1314, 5046, 19190, 72482, 272530, 1021734, 3823622, 14293234, 53394370, 199382550, 744348822, 2778471490, 10370520178, 38705706374, 144456761766, 539130777874, 2012086272674, 7509256255862, 28025026831158, 104591035618146
OFFSET
0,3
LINKS
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, arXiv:0911.2683 [math.CO], 2009.
FORMULA
G.f.: (1 - x)*(1 - 3*x)^2 / ((1 - 2*x)^2*(1 - 4*x + x^2)).
From Colin Barker, Oct 31 2017: (Start)
a(n) = (1/18)*(2*(3*2^n - (-3+sqrt(3))*(2+sqrt(3))^n + (2-sqrt(3))^n*(3+sqrt(3))) - 3*2^n*n).
a(n) = 8*a(n-1) - 21*a(n-2) + 20*a(n-3) - 4*a(n-4) for n>3.
(End)
EXAMPLE
There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.
MATHEMATICA
CoefficientList[Series[(1-x)*(1-3*x)^2/((1-2*x)^2*(1-4*x+x^2)), {x, 0, 50}], x] (* G. C. Greubel, Oct 22 2018 *)
PROG
(PARI) Vec((1 - x)*(1 - 3*x)^2 / ((1 - 2*x)^2*(1 - 4*x + x^2)) + O(x^30)) \\ Colin Barker, Oct 31 2017
(Magma) m:=50; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x)*(1-3*x)^2/((1-2*x)^2*(1-4*x+x^2)))); // G. C. Greubel, Oct 22 2018
CROSSREFS
Sequence in context: A116709 A165529 A116710 * A116707 A116704 A029759
KEYWORD
nonn,easy
AUTHOR
Vincent Vatter, Sep 21 2009
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Dec 09 2015
STATUS
approved