%I #32 Feb 05 2015 05:58:58

%S 1,1,2,2,2,4,6,10,20,36,66,132,250,478,956,1854,3612,7224,14178,27898,

%T 55796,110246,218166,436332,865618,1718902,3437804,6837398,13607250,

%U 27214500,54216128,108053078,216106156,431001044,859831354,1719662708,3432314834

%N Number of permutations p of {1,...,n} such that exactly one element of {p(1),...,p(i-1)} is between p(i) and p(i+1) for all i from 2 to n-1.

%H Alois P. Heinz, <a href="/A185030/b185030.txt">Table of n, a(n) for n = 0..1000</a>

%F a(n) ~ c * 2^n, where c = 0.049258776257798093135680343... - _Vaclav Kotesovec_, Feb 23 2014

%e a(3) = 2: 213, 231.

%e a(4) = 2: 2413, 3142.

%e a(5) = 4: 24135, 31524, 35142, 42531.

%e a(6) = 6: 251364, 315246, 361524, 416253, 462531, 526413.

%e a(7) = 10: 2513746, 2614753, 3162475, 3715246, 4172635, 4716253, 5173642, 5726413, 6274135, 6375142.

%e a(8) = 20: 25137468, 26138475, 27148635, 31624857, 31725864, 37152468, 37158642, 38162475, 41826357, 48172635, 51827364, 58173642, 61837524, 62841357, 62847531, 68274135, 68375142, 72851364, 73861524, 74862531.

%p b:= proc(u, o) option remember; `if`(u+o<2, 1,

%p `if`(o>1, b(sort([o-2, u+1])[]), 0)+

%p `if`(u>1, b(sort([u-2, o+1])[]), 0))

%p end:

%p a:= n-> `if`(n=0, 1, add(b(sort([j-1, n-j])[]), j=1..n)):

%p seq(a(n), n=0..40);

%t b[u_, o_] := b[u, o] = If[u+o<2, 1, If[o>1, b[Sequence @@ Sort[{o-2, u+1}]], 0] + If[u>1, b[Sequence @@ Sort[{u-2, o+1}]], 0]]; a[n_] := If[n == 0, 1, Sum[ b[Sequence @@ Sort[{j-1, n-j}]], {j, 1, n}]]; Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Feb 05 2015, after _Alois P. Heinz_ *)

%Y Cf. A174700, A174701, A174702, A174703, A174704, A174705, A174706, A174707, A174708, A216837.

%K nonn

%O 0,3

%A _Alois P. Heinz_, Oct 03 2013