cp's OEIS Frontend

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.

%I A187817 #12 Mar 15 2021 08:32:06
%S A187817 1,1,2,6,4,4,4,4,8,12,20,32,52,104,188,344,616,1116,2232,4236,8084,
%T A187817 15212,28760,57520,111512,216804,417560,806440,1612880,3162132,
%U A187817 6209192,12113136,23670168,47340336,93411704,184494460,362693224,713767712,1427535424
%N 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.
%H A187817 Alois P. Heinz, <a href="/A187817/b187817.txt">Table of n, a(n) for n = 0..1000</a>
%e A187817 a(4) = 4: 2314, 2341, 3214, 3241.
%e A187817 a(5) = 4: 23514, 32514, 34152, 43152.
%e A187817 a(6) = 4: 341625, 346152, 431625, 436152.
%e A187817 a(7) = 4: 3471625, 4371625, 4517263, 5417263.
%e A187817 a(8) = 8: 34716258, 43716258, 45182736, 45817263, 54182736, 54817263, 56283741, 65283741.
%e A187817 a(9) = 12: 348172596, 438172596, 451827369, 459182736, 541827369, 549182736, 561928374, 569283741, 651928374, 659283741, 672938514, 762938514.
%p A187817 b:= proc(u, o) option remember; `if`(u+o<3, (u+o)!,
%p A187817       `if`(o>2, b(sort([o-3, u+2])[]), 0)+
%p A187817       `if`(u>2, b(sort([u-3, o+2])[]), 0))
%p A187817     end:
%p A187817 a:= n-> `if`(n=0, 1, add(b(sort([j-1, n-j])[]), j=1..n)):
%p A187817 seq(a(n), n=0..40);
%t A187817 b[u_, o_] := b[u, o] = If[u + o < 3, (u + o)!,
%t A187817      If[o > 2, b @@ Sort[{o - 3, u + 2}], 0] +
%t A187817      If[u > 2, b @@ Sort[{u - 3, o + 2}], 0]];
%t A187817 a[n_] := If[n == 0, 1, Sum[b @@ Sort[{j - 1, n - j}], {j, 1, n}]];
%t A187817 a /@ Range[0, 40] (* _Jean-François Alcover_, Mar 15 2021, after _Alois P. Heinz_ *)
%Y A187817 Cf. A174700, A174701, A174702, A174703, A174704, A174705, A174706, A174707, A174708, A185030, A216837.
%K A187817 nonn
%O A187817 0,3
%A A187817 _Alois P. Heinz_, Oct 03 2013