A116720 Number of permutations of length n which avoid the patterns 213, 1234, 4312.

1, 1, 2, 5, 12, 25, 44, 69, 100, 137, 180, 229, 284, 345, 412, 485, 564, 649, 740, 837, 940, 1049, 1164, 1285, 1412, 1545, 1684, 1829, 1980, 2137, 2300, 2469, 2644, 2825, 3012, 3205, 3404, 3609, 3820, 4037, 4260, 4489, 4724, 4965, 5212, 5465, 5724, 5989, 6260

Offset

0,3

Links

Table of n, a(n) for n=0..48.

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

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

Formula

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

For n >= 3, a(n) = 3*n^2 - 14*n + 20. - Franklin T. Adams-Watters, Sep 16 2006

Maple

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

Mathematica

f[n_]:=n+(n+1)*(n+2)+(n+3)*(n+4)+(n+5)*(n+6); lst={1, 2}; Do[AppendTo[lst, f[n]], {n, -3, 5!}]; lst (* Vladimir Joseph Stephan Orlovsky, Oct 08 2009 *)
LinearRecurrence[{3, -3, 1}, {1, 2, 5, 12, 25}, 50] (* Harvey P. Dale, May 06 2017 *)

Crossrefs

Sequence in context: A322779 A096584 A002836 * A116731 A116722 A368638

Adjacent sequences: A116717 A116718 A116719 * A116721 A116722 A116723

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Extensions

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

a(0)=1 prepended by Alois P. Heinz, Aug 12 2025

Status

approved