A116825 Number of permutations of length n which avoid the patterns 1243, 2341, 4321.

1, 2, 6, 21, 71, 204, 479, 951, 1687, 2764, 4269, 6299, 8961, 12372, 16659, 21959, 28419, 36196, 45457, 56379, 69149, 83964, 101031, 120567, 142799, 167964, 196309, 228091, 263577, 303044, 346779, 395079, 448251, 506612, 570489, 640219, 716149, 798636

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 20.

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Formula

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

For n >= 6, a(n) = (5*n^4 - 16*n^3 + 43*n^2 - 752*n + 2388)/12. - Franklin T. Adams-Watters, Sep 16 2006

a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5). - Wesley Ivan Hurt, Sep 04 2022

Mathematica

CoefficientList[Series[(1 - 3*x + 6*x^2 + x^3 + 11*x^4 + 8*x^5 - 13*x^6 - 15*x^7 + 16*x^8 - 2*x^9)/(1 - x)^5, {x, 0, 40}], x] (* Wesley Ivan Hurt, Sep 04 2022 *)

Prog

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

Crossrefs

Sequence in context: A294719 A116795 A116766 * A116767 A116759 A116835

Adjacent sequences: A116822 A116823 A116824 * A116826 A116827 A116828

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved