A187817 - OEIS

%I #12 Mar 15 2021 08:32:06

%S 1,1,2,6,4,4,4,4,8,12,20,32,52,104,188,344,616,1116,2232,4236,8084,

%T 15212,28760,57520,111512,216804,417560,806440,1612880,3162132,

%U 6209192,12113136,23670168,47340336,93411704,184494460,362693224,713767712,1427535424

%N 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.

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

%e a(4) = 4: 2314, 2341, 3214, 3241.

%e a(5) = 4: 23514, 32514, 34152, 43152.

%e a(6) = 4: 341625, 346152, 431625, 436152.

%e a(7) = 4: 3471625, 4371625, 4517263, 5417263.

%e a(8) = 8: 34716258, 43716258, 45182736, 45817263, 54182736, 54817263, 56283741, 65283741.

%e a(9) = 12: 348172596, 438172596, 451827369, 459182736, 541827369, 549182736, 561928374, 569283741, 651928374, 659283741, 672938514, 762938514.

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

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

%p       `if`(u>2, b(sort([u-3, o+2])[]), 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 < 3, (u + o)!,

%t      If[o > 2, b @@ Sort[{o - 3, u + 2}], 0] +

%t      If[u > 2, b @@ Sort[{u - 3, o + 2}], 0]];

%t a[n_] := If[n == 0, 1, Sum[b @@ Sort[{j - 1, n - j}], {j, 1, n}]];

%t a /@ Range[0, 40] (* _Jean-François Alcover_, Mar 15 2021, after _Alois P. Heinz_ *)

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

%K nonn

%O 0,3

%A _Alois P. Heinz_, Oct 03 2013