A185030 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.

1, 1, 2, 2, 2, 4, 6, 10, 20, 36, 66, 132, 250, 478, 956, 1854, 3612, 7224, 14178, 27898, 55796, 110246, 218166, 436332, 865618, 1718902, 3437804, 6837398, 13607250, 27214500, 54216128, 108053078, 216106156, 431001044, 859831354, 1719662708, 3432314834

Offset: 0

Author

Alois P. Heinz, Oct 03 2013

Keywords

• nonn

Examples

			a(3) = 2: 213, 231.
a(4) = 2: 2413, 3142.
a(5) = 4: 24135, 31524, 35142, 42531.
a(6) = 6: 251364, 315246, 361524, 416253, 462531, 526413.
a(7) = 10: 2513746, 2614753, 3162475, 3715246, 4172635, 4716253, 5173642, 5726413, 6274135, 6375142.
a(8) = 20: 25137468, 26138475, 27148635, 31624857, 31725864, 37152468, 37158642, 38162475, 41826357, 48172635, 51827364, 58173642, 61837524, 62841357, 62847531, 68274135, 68375142, 72851364, 73861524, 74862531.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000

Crossrefs

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

Programs

Maple

b:= proc(u, o) option remember; `if`(u+o<2, 1,
      `if`(o>1, b(sort([o-2, u+1])[]), 0)+
      `if`(u>1, b(sort([u-2, o+1])[]), 0))
    end:
a:= n-> `if`(n=0, 1, add(b(sort([j-1, n-j])[]), j=1..n)):
seq(a(n), n=0..40);

Mathematica

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 *)

Formula

a(n) ~ c * 2^n, where c = 0.049258776257798093135680343... - Vaclav Kotesovec, Feb 23 2014