cp's OEIS Frontend

A232899 Number of permutations of [n] cyclically avoiding the consecutive step pattern UDU (U=up, D=down).

%I A232899 #21 Dec 19 2020 04:36:26
%S A232899 1,1,0,3,12,35,144,910,5976,39942,306570,2698223,25536132,257563618,
%T A232899 2813856192,33154390275,415692891552,5523237345701,77778820305558,
%U A232899 1157352664763569,18120617730892800,297774609082108662,5127157782095091402,92308888110570124310
%N A232899 Number of permutations of [n] cyclically avoiding the consecutive step pattern UDU (U=up, D=down).
%H A232899 Alois P. Heinz and Vaclav Kotesovec, <a href="/A232899/b232899.txt">Table of n, a(n) for n = 0..460</a> (first 200 terms from Alois P. Heinz)
%F A232899 a(n) ~ d^n * n!, where d = A245758 = 0.782704180171521701844707497734609... . - _Vaclav Kotesovec_, Aug 22 2014
%e A232899 a(2) = 0 because 12 and 21 do not avoid UDU (the two U's overlap).
%e A232899 a(3) = 3: 132, 213, 321.
%e A232899 a(4) = 12: 1243, 1342, 1432, 2134, 2143, 2431, 3124, 3214, 3421, 4213, 4312, 4321.
%e A232899 a(5) = 35: 12354, 12453, 12543, ..., 54213, 54312, 54321.
%p A232899 b:= proc(u, o, t) option remember; `if`(t=4, 0,
%p A232899      `if`(u+o=0, `if`(t=2, 0, 1),
%p A232899       add(b(u+j-1, o-j, [2, 2, 4][t]), j=1..o)+
%p A232899       add(b(u-j, o+j-1, [1, 3, 1][t]), j=1..u)))
%p A232899     end:
%p A232899 a:= n-> `if`(n<2, 1, n*b(0, n-1, 1)):
%p A232899 seq(a(n), n=0..30);
%t A232899 b[u_, o_, t_] := b[u, o, t] = If[t == 4, 0,
%t A232899     If[u + o == 0, If[t == 2, 0, 1],
%t A232899     Sum[b[u + j - 1, o - j, {2, 2, 4}[[t]]], {j, 1, o}] +
%t A232899     Sum[b[u - j, o + j - 1, {1, 3, 1}[[t]]], {j, 1, u}]]];
%t A232899 a[n_] := If[n < 2, 1, n b[0, n - 1, 1]];
%t A232899 a /@ Range[0, 30] (* _Jean-François Alcover_, Dec 19 2020, after _Alois P. Heinz_ *)
%Y A232899 Column k=0 of A232933.
%Y A232899 Cf. A177477, A245758.
%K A232899 nonn
%O A232899 0,4
%A A232899 _Alois P. Heinz_, Dec 02 2013