A116718 Number of permutations of length n which avoid the patterns 321, 1342, 3124.

1, 1, 2, 5, 12, 22, 37, 60, 96, 153, 244, 390, 625, 1004, 1616, 2605, 4204, 6790, 10973, 17740, 28688, 46401, 75060, 121430, 196457, 317852, 514272, 832085, 1346316, 2178358, 3524629, 5702940, 9227520, 14930409, 24157876, 39088230, 63246049, 102334220

Offset

0,3

Links

Table of n, a(n) for n=0..37.

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

Index entries for linear recurrences with constant coefficients, signature (3, -2, -1, 1).

Formula

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

a(0)=1, a(1)=1, a(2)=2, a(3)=5, a(4)=12, a(5)=22, a(6)=37, a(n)=3*a(n-1)- 2*a(n-2)- a(n-3)+a (n-4). - Harvey P. Dale, Oct 21 2011

a(n) = F(n+3) + 2*n - 9 for n>2, where F is A000045. - Jason Kimberley, Nov 22 2013

For n>2, a(n) = (1+2/sqrt(5))*((1+sqrt(5))/2)^n + (1-2/sqrt(5))*((1-sqrt(5))/2)^n + 2*n - 9. - Vaclav Kotesovec, Dec 11 2013

Mathematica

Rest[CoefficientList[Series[1+((x+1)(2x^4+x^3-3x^2+2x-1)x)/((x-1)^2 (x^2+ x-1)), {x, 0, 50}], x]] (* or *) Join[{1, 1, 2}, LinearRecurrence[{3, -2, -1, 1}, {5, 12, 22, 37}, 50]] (* Harvey P. Dale, Oct 21 2011 *)

Crossrefs

Sequence in context: A116727 A116729 A048840 * A026035 A215183 A086734

Adjacent sequences: A116715 A116716 A116717 * A116719 A116720 A116721

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved