A116730 Number of permutations of length n which avoid the patterns 321, 1342, 1423.

1, 2, 5, 12, 25, 48, 87, 152, 259, 434, 719, 1182, 1933, 3150, 5121, 8312, 13477, 21836, 35363, 57252, 92671, 149982, 242715, 392762, 635545, 1028378, 1663997, 2692452, 4356529, 7049064, 11405679, 18454832, 29860603, 48315530, 78176231, 126491862, 204668197

Offset

1,2

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

Formula

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

a(n) = 2*A000045(n+3)-3*n-2. - R. J. Mathar, Aug 05 2008

From Colin Barker, Oct 20 2017: (Start)

a(n) = 1 + (2^(1-n)*((1-sqrt(5))^n*(-2+sqrt(5)) + (1+sqrt(5))^n*(2+sqrt(5))))/sqrt(5) - 3*(1 + n).

a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4) for n>4.

(End)

Prog

(PARI) Vec(x*(1 - x + x^2 + 2*x^3) / ((1 - x)^2*(1 - x - x^2)) + O(x^40)) \\ Colin Barker, Oct 20 2017

Crossrefs

Sequence in context: A116731 A116722 A368638 * A240847 A166106 A067331

Adjacent sequences: A116727 A116728 A116729 * A116731 A116732 A116733

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Extensions

Extended beyond a(30) by R. J. Mathar, Aug 05 2008

Status

approved