A165530 Number of permutations of length n which avoid the patterns 4321 and 3142.
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
Examples
There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.
Links
- Colin Barker, Table of n, a(n) for n = 0..1000
- 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.
- Wikipedia, Permutation classes avoiding two patterns of length 4.
- Index entries for linear recurrences with constant coefficients, signature (8,-21,20,-4).
Programs
-
Magma
m:=50; R
:=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 -
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 *) -
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
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)
Extensions
a(0)=1 prepended by Alois P. Heinz, Dec 09 2015