A116710 Number of permutations of length n which avoid the patterns 1423, 3421.

1, 2, 6, 22, 86, 337, 1299, 4910, 18228, 66640, 240550, 859295, 3043525, 10705182, 37441618, 130351650, 452119862, 1563402141, 5392828631, 18564966510, 63807048144, 219015409556, 750968486726, 2572756726459, 8808011192329, 30138217809470, 103077794599470

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 (11,-47,99,-109,63,-18,2).

Formula

G.f.: x*(1 - 9*x + 31*x^2 - 49*x^3 + 37*x^4 - 14*x^5 + 2*x^6) / ((1 - x)*(1 - 3*x + x^2)^2*(1 - 4*x + 2*x^2)).

Prog

(PARI) Vec(x*(1 - 9*x + 31*x^2 - 49*x^3 + 37*x^4 - 14*x^5 + 2*x^6) / ((1 - x)*(1 - 3*x + x^2)^2*(1 - 4*x + 2*x^2)) + O(x^30)) \\ Colin Barker, Oct 23 2017

Crossrefs

Sequence in context: A165528 A116709 A165529 * A165530 A116707 A116704

Adjacent sequences: A116707 A116708 A116709 * A116711 A116712 A116713

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved