A116704 Number of permutations of length n which avoid the patterns 2341, 4312.

1, 1, 2, 6, 22, 86, 338, 1318, 5110, 19770, 76466, 295810, 1144530, 4428622, 17136186, 66306722, 256565926, 992749334, 3841316550, 14863484902, 57512368162, 222536820262, 861078033110, 3331832349354, 12892103081874, 49884359171762

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.

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,-17,22,-13,4).

Formula

G.f.: (x^5-5*x^4+13*x^3-12*x^2+6*x-1) / (4*x^5-13*x^4+22*x^3-17*x^2+7*x-1). (corrected by Jay Pantone, Feb 18 2016)

a(n) = 7*a(n-1) - 17*a(n-2) + 22*a(n-3) - 13*a(n-4) + 4*a(n-5) for n>6. - Colin Barker, Oct 25 2017

Prog

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

Crossrefs

Sequence in context: A116710 A165530 A116707 * A029759 A150255 A107243

Adjacent sequences: A116701 A116702 A116703 * A116705 A116706 A116707

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Extensions

Prepended a(0)=1 by Joerg Arndt, Feb 18 2016

Status

approved