%I #20 Jun 06 2013 17:02:42
%S 2,2,8,16,44,108,284,740,1966,5254,14172,38476,105122,288754,797036,
%T 2209588,6149618,17176186,48129284,135261796,381169532,1076824852,
%U 3049109912,8652239496,24600592454,70075316198,199955694616
%N Number of simple skew-merged permutations with n elements.
%C 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.
%H Vincenzo Librandi, <a href="/A220589/b220589.txt">Table of n, a(n) for n = 4..1000</a>
%H Michael H. Albert and Vincent Vatter, <a href="http://www.math.ufl.edu/~vatter/publications/simple-generation/">Generating and enumerating 321-avoiding and skew-merged simple permutations</a>
%F G.f.: (1-2*x-x^2+(x-1)*sqrt(1-2*x-3*x^2)) / (x+1).
%F 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
%F a(n) ~ 3^(n-1/2)/(2*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Jan 16 2013
%t 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 *)
%Y Cf. A029759.
%K nonn,easy
%O 4,1
%A _Vincent Vatter_, Jan 14 2013
|