A116715 Number of permutations of length n which avoid the patterns 312, 2341, 4321.

1, 2, 5, 12, 25, 54, 120, 265, 580, 1272, 2796, 6143, 13488, 29619, 65053, 142873, 313771, 689095, 1513390, 3323699, 7299465, 16031000, 35207128, 77321545, 169812767, 372941033, 819049274, 1798787604, 3950478790, 8676000808, 19054143661, 41846514135

Offset

1,2

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 (1,1,2,3,1).

Formula

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

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

Prog

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

Crossrefs

Sequence in context: A122439 A063807 A182202 * A117177 A287141 A214610

Adjacent sequences: A116712 A116713 A116714 * A116716 A116717 A116718

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved