A187817 Number of permutations p of {1,...,n} such that exactly two elements of {p(1),...,p(i-1)} are between p(i) and p(i+1) for all i from 3 to n-1.

1, 1, 2, 6, 4, 4, 4, 4, 8, 12, 20, 32, 52, 104, 188, 344, 616, 1116, 2232, 4236, 8084, 15212, 28760, 57520, 111512, 216804, 417560, 806440, 1612880, 3162132, 6209192, 12113136, 23670168, 47340336, 93411704, 184494460, 362693224, 713767712, 1427535424

Offset: 0

Author

Alois P. Heinz, Oct 03 2013

Keywords

• nonn

Examples

			a(4) = 4: 2314, 2341, 3214, 3241.
a(5) = 4: 23514, 32514, 34152, 43152.
a(6) = 4: 341625, 346152, 431625, 436152.
a(7) = 4: 3471625, 4371625, 4517263, 5417263.
a(8) = 8: 34716258, 43716258, 45182736, 45817263, 54182736, 54817263, 56283741, 65283741.
a(9) = 12: 348172596, 438172596, 451827369, 459182736, 541827369, 549182736, 561928374, 569283741, 651928374, 659283741, 672938514, 762938514.
		

Links

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

Crossrefs

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

Programs

Maple

b:= proc(u, o) option remember; `if`(u+o<3, (u+o)!,
      `if`(o>2, b(sort([o-3, u+2])[]), 0)+
      `if`(u>2, b(sort([u-3, o+2])[]), 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 < 3, (u + o)!,
     If[o > 2, b @@ Sort[{o - 3, u + 2}], 0] +
     If[u > 2, b @@ Sort[{u - 3, o + 2}], 0]];
a[n_] := If[n == 0, 1, Sum[b @@ Sort[{j - 1, n - j}], {j, 1, n}]];
a /@ Range[0, 40] (* Jean-François Alcover, Mar 15 2021, after Alois P. Heinz *)