A116699 Number of permutations of length n which avoid the patterns 123 and 4312.

1, 2, 5, 13, 30, 61, 112, 190, 303, 460, 671, 947, 1300, 1743, 2290, 2956, 3757, 4710, 5833, 7145, 8666, 10417, 12420, 14698, 17275, 20176, 23427, 27055, 31088, 35555, 40486, 45912, 51865, 58378, 65485, 73221, 81622, 90725, 100568, 111190, 122631, 134932

Offset: 1

Author

Lara Pudwell, Feb 26 2006

Keywords

• nonn
• easy

Comments

Also number of permutations of length n which avoid the patterns 321, 2134 (reverse symmetry); or 321, 1243 (complement symmetry); etc.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Christian Bean, Bjarki Gudmundsson, Henning Ulfarsson, Automatic discovery of structural rules of permutation classes, arXiv:1705.04109 [math.CO], 2017.
• Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.
• Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Programs

Magma

[(n^4 + 2*n^3 - 13*n^2 + 34*n)/24: n in [1..45]]; // Vincenzo Librandi, Nov 01 2014

Mathematica

LinearRecurrence[{5,-10,10,-5,1}, {1,2,5,13,30}, 50] (* Vladimir Joseph Stephan Orlovsky, Feb 02 2012 *)
CoefficientList[Series[(2 x^3 - 5 x^2 + 3 x - 1)/(x - 1)^5, {x, 0, 40}], x] (* Vincenzo Librandi, Nov 01 2014 *)

PARI

for(n=1,100,print1((n^4 + 2*n^3 - 13*n^2 + 34*n)/24",")) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 22 2008

Formula

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

a(n) = (n^4 + 2*n^3 - 13*n^2 + 34*n)/24. - Franklin T. Adams-Watters, Sep 16 2006

Partial sums of A105163. - Levi R. Self (levi.r.self(AT)gmail.com), Aug 04 2007

Binomial transform of [1, 1, 2, 3, 1, 0, 0, 0, ...]. - Gary W. Adamson, Oct 23 2007

Extensions

Edited by N. J. A. Sloane, Mar 16 2008

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 22 2008