A116837 Number of permutations of length n which avoid the patterns 3421, 4123, 4312; or avoid the patterns 2341, 3142, 3214.

1, 2, 6, 21, 73, 250, 853, 2911, 9938, 33931, 115849, 395534, 1350437, 4610679, 15741842, 53746011, 183500361, 626509422, 2139036965, 7303129015, 24934442130, 85131510491, 290657157705, 992365609838, 3388148123941

Offset

1,2

Links

Table of n, a(n) for n=1..25.

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

Index entries for linear recurrences with constant coefficients, signature (5,-7,6,-2).

Formula

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

Mathematica

CoefficientList[Series[-(x - 1)^3/((x^2 - x + 1) (2 x^2 - 4 x + 1)), {x, 0, 30}], x] (* Wesley Ivan Hurt, Dec 28 2023 *)

Crossrefs

Sequence in context: A116760 A116828 A294764 * A116781 A047106 A360152

Adjacent sequences: A116834 A116835 A116836 * A116838 A116839 A116840

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved