A116709 Number of permutations of length n which avoid the patterns 2341, 4213.

1, 2, 6, 22, 86, 336, 1290, 4870, 18164, 67234, 247786, 911120, 3346618, 12286942, 45104548, 165573482, 607817410, 2231360192, 8191763970, 30074097062, 110410946820, 405353571346, 1488185247962, 5463619641904, 20058759689642, 73642362774478, 270365534734372

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 (8,-22,25,-10,2).

Formula

G.f.: -x*(2*x^4-7*x^3+12*x^2-6*x+1) / (2*x^5-10*x^4+25*x^3-22*x^2+8*x-1).

a(n) = 8*a(n-1) - 22*a(n-2) + 25*a(n-3) - 10*a(n-4) + 2*a(n-5) for n>5. - Colin Barker, Oct 20 2017

Prog

(PARI) Vec(x*(1 - 6*x + 12*x^2 - 7*x^3 + 2*x^4) / (1 - 8*x + 22*x^2 - 25*x^3 + 10*x^4 - 2*x^5) + O(x^30)) \\ Colin Barker, Oct 20 2017

Crossrefs

Sequence in context: A165526 A165527 A165528 * A165529 A116710 A165530

Adjacent sequences: A116706 A116707 A116708 * A116710 A116711 A116712

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved