A178594 Number of permutations of length n avoiding each length 5 pattern p with p(1)=5 and (p(5)=4 or p(4)=4).

0, 1, 2, 6, 24, 108, 516, 2556, 12972, 66996, 350628, 1854252, 9888924, 53107236, 286882740, 1557510012, 8492587596, 46483203348, 255273601860, 1406078670924, 7765563869436, 42991470093060, 238528474655316, 1326059132006556

Offset

0,3

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Elena Barcucci, Vincent Vajnovszki, Generalized Schroeder permutations, Theoretical Computer Science, Volume 502, 2 September 2013, Pages 210-216.

Formula

Generating function: (1+2*x+3*x*(-x+1-(1-6*x+x^2)^(1/2))/(x+(1-6*x+x^2)^(1/2)))*x.

Recurrence (for n>=5): (n-2)*a(n) = 3*(4*n - 11)*a(n-1) - (37*n - 131)*a(n-2) + 6*(n-5)*a(n-3). - Vaclav Kotesovec, Nov 20 2012

a(n) ~ 3*sqrt(3*sqrt(2)-4)*(3+2*sqrt(2))^n/(n^(3/2)*sqrt(Pi)). - Vaclav Kotesovec, Nov 20 2012

Mathematica

CoefficientList[Series[x(1 + 2x + 3x(-x + 1 - (1 - 6x + x^2)^(1/2))/(x + (1 - 6x + x^2)^(1/2))), {x, 0, 23}], x] (* Robert G. Wilson v, Jun 28 2010 *)

Prog

(PARI) x='x+O('x^50); concat([0], Vec((1+2*x+3*x*(-x+1-(1-6*x+x^2)^(1/2))/(x+(1-6*x+x^2)^(1/2)))*x)) \\ G. C. Greubel, Mar 24 2017

Crossrefs

Sequence in context: A163824 A356782 A094433 * A277248 A189840 A189255

Adjacent sequences: A178591 A178592 A178593 * A178595 A178596 A178597

Keyword

nonn

Author

Vincent Vajnovszki (vvajnov(AT)u-bourgogne.fr), May 30 2010

Extensions

a(19) onward from Robert G. Wilson v, Jun 28 2010

Status

approved