A116775 Number of permutations of length n which avoid the patterns 1234, 2341, 4132.

1, 2, 6, 21, 72, 221, 605, 1517, 3574, 8065, 17671, 37953, 80424, 168885, 352481, 732581, 1518074, 3139033, 6480187, 13360153, 27514476, 56610861, 116377941, 239059421, 490715582, 1006612721, 2063574895, 4227833137, 8657015344, 17716708965, 36238752201

Offset

1,2

Links

Colin Barker, Table of n, a(n) for n = 1..1000

D. Callan, T. Mansour, Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns, arXiv:1705.00933 (2017), Table 2 No 42.

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

Index entries for linear recurrences with constant coefficients, signature (8,-26,44,-41,20,-4)

Formula

G.f.: x*(1 - 6*x + 16*x^2 - 19*x^3 + 13*x^4 - 11*x^5 - 5*x^6 + 4*x^7) / ((1 - x)^4*(1 - 2*x)^2).

From Colin Barker, Oct 06 2017: (Start)

a(n) = (6*(-44+21*2^n) + (-56+9*2^n)*n + 12*n^2 - 28*n^3) / 24 for n>2.

a(n) = 8*a(n-1) - 26*a(n-2) + 44*a(n-3) - 41*a(n-4) + 20*a(n-5) - 4*a(n-6) for n>8.

(End)

Prog

(PARI) Vec(x*(1 - 6*x + 16*x^2 - 19*x^3 + 13*x^4 - 11*x^5 - 5*x^6 + 4*x^7) / ((1 - x)^4*(1 - 2*x)^2) + O(x^50)) \\ Colin Barker, Oct 06 2017

Crossrefs

Sequence in context: A294754 A116750 A116791 * A116786 A116748 A116812

Adjacent sequences: A116772 A116773 A116774 * A116776 A116777 A116778

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved