A116706 Number of permutations of length n which avoid the patterns 2134, 3421.

1, 2, 6, 22, 86, 330, 1206, 4174, 13726, 43134, 130302, 380414, 1078270, 2978814, 8046590, 21311486, 55468030, 142147582, 359268350, 896794622, 2213543934, 5408292862, 13091995646, 31424774142, 74845257726, 176991240190, 415789744126, 970830381054

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,-50,120,-160,112,-32).

Formula

G.f.: x*(1 - 9*x + 34*x^2 - 64*x^3 + 64*x^4 - 28*x^5 + 4*x^6) / ((1 - x)*(1 - 2*x)^5)

From Colin Barker, Oct 20 2017: (Start)

a(n) = (24*(-32+39*2^n) - 263*2^(1+n)*n + 165*2^n*n^2 - 13*2^(1+n)*n^3 + 3*2^n*n^4) / 384 for n>1.

a(n) = 11*a(n-1) - 50*a(n-2) + 120*a(n-3) - 160*a(n-4) + 112*a(n-5) - 32*a(n-6) for n>7.

(End)

Prog

(PARI) Vec(x*(1 - 9*x + 34*x^2 - 64*x^3 + 64*x^4 - 28*x^5 + 4*x^6) / ((1 - x)*(1 - 2*x)^5) + O(x^30)) \\ Colin Barker, Oct 20 2017

Crossrefs

Sequence in context: A079104 A116705 A116708 * A165524 A165525 A165526

Adjacent sequences: A116703 A116704 A116705 * A116707 A116708 A116709

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved