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
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).
Programs
-
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
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