OFFSET
0,3
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.
Index entries for linear recurrences with constant coefficients, signature (8,-21,20,-4).
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
KEYWORD
nonn,easy
AUTHOR
Vincent Vatter, Sep 21 2009
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Dec 09 2015
STATUS
approved