login
A116718
Number of permutations of length n which avoid the patterns 321, 1342, 3124.
0
1, 1, 2, 5, 12, 22, 37, 60, 96, 153, 244, 390, 625, 1004, 1616, 2605, 4204, 6790, 10973, 17740, 28688, 46401, 75060, 121430, 196457, 317852, 514272, 832085, 1346316, 2178358, 3524629, 5702940, 9227520, 14930409, 24157876, 39088230, 63246049, 102334220
OFFSET
0,3
FORMULA
G.f.: 1+(x+1)*(2*x^4+x^3-3*x^2+2*x-1)*x/((x-1)^2*(x^2+x-1)).
a(0)=1, a(1)=1, a(2)=2, a(3)=5, a(4)=12, a(5)=22, a(6)=37, a(n)=3*a(n-1)- 2*a(n-2)- a(n-3)+a (n-4). - Harvey P. Dale, Oct 21 2011
a(n) = F(n+3) + 2*n - 9 for n>2, where F is A000045. - Jason Kimberley, Nov 22 2013
For n>2, a(n) = (1+2/sqrt(5))*((1+sqrt(5))/2)^n + (1-2/sqrt(5))*((1-sqrt(5))/2)^n + 2*n - 9. - Vaclav Kotesovec, Dec 11 2013
MATHEMATICA
Rest[CoefficientList[Series[1+((x+1)(2x^4+x^3-3x^2+2x-1)x)/((x-1)^2 (x^2+ x-1)), {x, 0, 50}], x]] (* or *) Join[{1, 1, 2}, LinearRecurrence[{3, -2, -1, 1}, {5, 12, 22, 37}, 50]] (* Harvey P. Dale, Oct 21 2011 *)
CROSSREFS
Sequence in context: A116727 A116729 A048840 * A026035 A215183 A086734
KEYWORD
nonn,easy
AUTHOR
Lara Pudwell, Feb 26 2006
STATUS
approved