A116728 Number of permutations of length n which avoid the patterns 321, 1243, 2134.

1, 2, 5, 12, 19, 26, 33, 40, 47, 54, 61, 68, 75, 82, 89, 96, 103, 110, 117, 124, 131, 138, 145, 152, 159, 166, 173, 180, 187, 194, 201, 208, 215, 222, 229, 236, 243, 250, 257, 264, 271, 278, 285, 292, 299, 306, 313, 320, 327, 334, 341, 348, 355, 362, 369

Offset: 1

Author

Lara Pudwell, Feb 26 2006

Keywords

• nonn
• easy

Links

• Nathaniel Johnston, Table of n, a(n) for n = 1..5000
• Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.
• Index entries for linear recurrences with constant coefficients, signature (2,-1).

Crossrefs

Cf. A017041.

Programs

Maple

t := taylor((4*x^3+2*x^2+1)*x/(x-1)^2,x,51):seq(coeff(t,x,n),n=1..50); # Nathaniel Johnston, Apr 27 2011

PARI

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

Formula

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

For n >= 3, a(n) = 7*n - 16. - Franklin T. Adams-Watters, Sep 16 2006

a(n) = 2*a(n-1) - a(n-2) for n=4. - Colin Barker, Oct 24 2017

a(n) = A017041(n-3) for n > 2. - Georg Fischer, Oct 07 2018

E.g.f.: exp(x)*(7*x - 16) + 2*(x^2 + 5*x + 8). - Stefano Spezia, Oct 10 2022