|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (1 - x)*(1 - 3*x)^2 / ((1 - 2*x)^2*(1 - 4*x + x^2)).
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
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|