A116716 Number of permutations of length n which avoid the patterns 321, 2341, 4123.

1, 2, 5, 12, 26, 58, 131, 295, 662, 1487, 3342, 7510, 16874, 37915, 85195, 191432, 430143, 966522, 2171756, 4879892, 10965017, 24638169, 55361464, 124396081, 279515456, 628065528, 1411250432, 3171050937, 7125286777, 16010374058, 35974983957, 80835055196

Offset

1,2

Links

Colin Barker, Table of n, a(n) for n = 1..1000

David Lonoff and Jonah Ostroff, Symmetric Permutations Avoiding Two Patterns, Annals of Combinatorics 14 (1) pp.143-158 Springer, 2010; . - N. J. A. Sloane, Dec 27 2012

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

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

Formula

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

a(n) = 2*a(n-1) + a(n-3) + a(n-4) - a(n-5) for n>5. - Colin Barker, Oct 20 2017

Prog

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

Crossrefs

Sequence in context: A073778 A033490 A221950 * A128812 A241692 A078410

Adjacent sequences: A116713 A116714 A116715 * A116717 A116718 A116719

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved