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

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

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)

Prog

(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

Crossrefs

Sequence in context: A116844 A116851 A038989 * A116847 A116848 A370800

Adjacent sequences: A116847 A116848 A116849 * A116851 A116852 A116853

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved