A116708 Number of permutations of length n which avoid the patterns 2314, 4321.

1, 2, 6, 22, 86, 330, 1198, 4087, 13185, 40619, 120636, 348197, 983073, 2728722, 7475575, 20274288, 54558291, 145933414, 388520823, 1030601705, 2726043970, 7194657991, 18955376065, 49872709551, 131077883030, 344216450494, 903332924312, 2369406020786

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 (13,-74,243,-510,715,-678,429,-173,40,-4).

Formula

G.f.: -x*(4*x^9-29*x^8+108*x^7-234*x^6+313*x^5-268*x^4+151*x^3-54*x^2+11*x-1) / ((x-1)^6*(2*x-1)^2*(x^2-3*x+1)).

Prog

(PARI) Vec((1 - 11*x + 54*x^2 - 151*x^3 + 268*x^4 - 313*x^5 + 234*x^6 - 108*x^7 + 29*x^8 - 4*x^9) / ((1 - x)^6*(1 - 2*x)^2*(1 - 3*x + x^2)) + O(x^30)) \\ Colin Barker, Oct 20 2017

Crossrefs

Sequence in context: A079105 A079104 A116705 * A116706 A165524 A165525

Adjacent sequences: A116705 A116706 A116707 * A116709 A116710 A116711

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved