OFFSET
4,1
COMMENTS
A permutation is skew-merged if it is the union of an increasing subsequence and a decreasing subsequence. A permutation is simple if it does not contain a nontrivial interval.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 4..1000
Michael H. Albert and Vincent Vatter, Generating and enumerating 321-avoiding and skew-merged simple permutations
FORMULA
G.f.: (1-2*x-x^2+(x-1)*sqrt(1-2*x-3*x^2)) / (x+1).
Recurrence (for n>4): (n-4)*n*a(n) = (n^2-7*n+15)*a(n-1) + (n-3)*(5*n-17)*a(n-2) + 3*(n-4)*(n-3)*a(n-3). - Vaclav Kotesovec, Jan 16 2013
a(n) ~ 3^(n-1/2)/(2*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jan 16 2013
MATHEMATICA
Rest[Rest[Rest[Rest[CoefficientList[Series[(1-2*x-x^2+(x-1)*Sqrt[1-2*x-3*x^2])/(x+1), {x, 0, 20}], x]]]]] (* Vaclav Kotesovec, Jan 16 2013 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Vincent Vatter, Jan 14 2013
STATUS
approved