A116707 Number of permutations of length n which avoid the patterns 1342, 4213.

1, 2, 6, 22, 86, 338, 1318, 5106, 19718, 76066, 293398, 1131794, 4366374, 16846018, 64995254, 250765298, 967503814, 3732821922, 14401956182, 55565542354, 214382633062, 827129764994, 3191227078902, 12312373271986, 47503525349126, 183277819294562

Offset

1,2

Links

Colin Barker, Table of n, a(n) for n = 1..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.

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

Wikipedia, Permutation classes avoiding two patterns of length 4.

Index entries for linear recurrences with constant coefficients, signature (7,-16,16,-4).

Formula

G.f.: -x*(x-1)*(2*x-1)^2 / (4*x^4-16*x^3+16*x^2-7*x+1).

a(n) = 7*a(n-1) - 16*a(n-2) + 16*a(n-3) - 4*a(n-4) for n>3. - Colin Barker, Oct 20 2017

Mathematica

CoefficientList[Series[-(x - 1)*(2*x - 1)^2/(4*x^4 - 16*x^3 + 16*x^2 - 7*x + 1), {x, 0, 30}], x] (* Wesley Ivan Hurt, Sep 04 2022 *)

Prog

(PARI) Vec(x*(1 - x)*(1 - 2*x)^2 / (1 - 7*x + 16*x^2 - 16*x^3 + 4*x^4) + O(x^40)) \\ Colin Barker, Oct 20 2017

Crossrefs

Sequence in context: A165529 A116710 A165530 * A116704 A029759 A150255

Adjacent sequences: A116704 A116705 A116706 * A116708 A116709 A116710

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved