A116721 Number of permutations of length n which avoid the patterns 123, 3142, 4312; or avoid the patterns 123, 3421, 4231.

1, 2, 5, 12, 24, 42, 67, 100, 142, 194, 257, 332, 420, 522, 639, 772, 922, 1090, 1277, 1484, 1712, 1962, 2235, 2532, 2854, 3202, 3577, 3980, 4412, 4874, 5367, 5892, 6450, 7042, 7669, 8332, 9032, 9770, 10547, 11364, 12222, 13122, 14065, 15052, 16084, 17162

Offset: 1

Author

Lara Pudwell, Feb 26 2006

Keywords

• nonn
• easy

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.
• Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Programs

Maple

A116721 := proc(n) coeftayl(-x*(x^4-3*x^2+2*x-1)/(x-1)^4,x=0,n) ; end: seq(A116721(n),n=1..60) ; # R. J. Mathar, Jan 23 2008

PARI

Vec(x*(1 - 2*x + 3*x^2 - x^4) / (1 - x)^4 + O(x^100)) \\ Colin Barker, Oct 24 2017

Formula

G.f.: x*(1 - 2*x + 3*x^2 - x^4) / (1 - x)^4.

For n >= 2, a(n) = (n^3 + 3n^2 - 16n + 24)/6. - Franklin T. Adams-Watters, Sep 16 2006

a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4) for n>5. - Colin Barker, Oct 24 2017

Extensions

More terms from R. J. Mathar, Jan 23 2008