A116850 Number of permutations of length n which avoid the patterns 231, 12354.

1, 2, 5, 14, 41, 119, 334, 902, 2351, 5945, 14660, 35408, 84061, 196715, 454778, 1040522, 2359451, 5308589, 11862208, 26345684, 58196201, 127926527, 279970070, 610271534, 1325400391, 2868904289, 6190793084, 13321109912, 28588376501, 61203284435, 130728067570

Offset: 1

Author

Lara Pudwell, Feb 26 2006

Keywords

• nonn
• easy

Comments

Inverse binomial transform (offset 0) is: 0, 1, 0, 2, 2, 6, 7, 12, 14, 20, 23, 30, 34, 42, 47, 56, 62, 72,.. with difference pattern +1, -1, +2, +0, +4, +1, +5, +2, +6, +3,... as in A168230. - R. J. Mathar, Feb 23 2013

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 (9,-33,63,-66,36,-8).

Programs

PARI

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

Formula

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

From Colin Barker, Oct 30 2017: (Start)

a(n) = (1/16)*(32-9*2^(1+n) + (8+2^n)*n + (8+2^n)*n^2).

a(n) = 9*a(n-1) - 33*a(n-2) + 63*a(n-3) - 66*a(n-4) + 36*a(n-5) - 8*a(n-6) for n>6.

(End)