A116734 Number of permutations of length n which avoid the patterns 231, 1432, 4123.

1, 2, 5, 12, 25, 50, 97, 184, 345, 642, 1189, 2196, 4049, 7458, 13729, 25264, 46481, 85506, 157285, 289308, 532137, 978770, 1800257, 3311208, 6090281, 11201794, 20603333, 37895460, 69700641, 128199490, 235795649, 433695840, 797691041

Offset

1,2

Links

Harvey P. Dale, 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, 0, -1, 1).

Formula

G.f.: A(x) = -{x(x^2+x^3+1-x)}/{(x-1)^2(x^3+x^2+x-1)}

a(n)=A000213(n+2)-n-1. [From R. J. Mathar, Aug 05 2008]

a(0)=0, a(1)=1, a(2)=2, then a(n) = a(n-1) + a(n-2) + a(n-3) + 2*n - 4. [From Gerald McGarvey, Oct 06 2009]

Mathematica

LinearRecurrence[{3, -2, 0, -1, 1}, {1, 2, 5, 12, 25}, 40] (* Harvey P. Dale, Jan 21 2016 *)

Crossrefs

Sequence in context: A240847 A166106 A067331 * A101836 A262667 A122439

Adjacent sequences: A116731 A116732 A116733 * A116735 A116736 A116737

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Extensions

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

Status

approved