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,2

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

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

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

Prog

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

Crossrefs

Cf. A017041.

Sequence in context: A131091 A356490 A336462 * A276478 A333558 A095306

Adjacent sequences: A116725 A116726 A116727 * A116729 A116730 A116731

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved