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

Author

Lara Pudwell, Feb 26 2006

Keywords

• nonn
• easy

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

Programs

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

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