A116711 Number of permutations of length n which avoid the patterns 123, 3214, 4312.

1, 2, 5, 12, 23, 36, 51, 68, 87, 108, 131, 156, 183, 212, 243, 276, 311, 348, 387, 428, 471, 516, 563, 612, 663, 716, 771, 828, 887, 948, 1011, 1076, 1143, 1212, 1283, 1356, 1431, 1508, 1587, 1668, 1751, 1836, 1923, 2012, 2103, 2196, 2291, 2388, 2487, 2588

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

Programs

PARI

Vec(x*(1 - x + 2*x^2 + 2*x^3 - 2*x^5) / (1 - x)^3 + O(x^50)) \\ Colin Barker, Oct 23 2017

Formula

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

For n >= 4, a(n) = n^2 + 2*n - 12. - Franklin T. Adams-Watters, Sep 16 2006

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