cp's OEIS Frontend

A242785 Number of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

%I A242785 #11 Mar 23 2021 16:13:07
%S A242785 1,1,2,5,21,70,450,4326,34944,209863,1573632,21824925,302273664,
%T A242785 2854894485,60269056512,1207441809209,19346879737625,252773481889854,
%U A242785 2918333808555034,69792946997645295,982945842995115000,16085109561896603059,402131210857811703926
%N A242785 Number of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.
%H A242785 Alois P. Heinz, <a href="/A242785/b242785.txt">Table of n, a(n) for n = 0..150</a>
%e A242785 a(4) = 21 because there are 4! = 24 permutations of {1,2,3,4} and only 3 of them do not avoid the consecutive step pattern up, down, down given by the binary expansion of 4 = 100_2: (1,4,3,2), (2,4,3,1), (3,4,2,1).
%p A242785 a:= proc(n) option remember; local b, m, r, h;
%p A242785       if n<2 then return 1 fi;
%p A242785       m:= iquo(n, 2, 'r'); h:= 2^ilog2(n);
%p A242785       b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
%p A242785       `if`(t=m and r=0, 0, add(b(u-j, o+j-1, irem(2*t, h)), j=1..u))+
%p A242785       `if`(t=m and r=1, 0, add(b(u+j-1, o-j, irem(2*t+1, h)), j=1..o)))
%p A242785       end; forget(b);
%p A242785       b(n, 0, 0)
%p A242785     end:
%p A242785 seq(a(n), n=0..30);
%t A242785 a[n_] := a[n] = Module[{b, m, r, h},
%t A242785      If[n < 2, Return[1]]; {m, r} = QuotientRemainder[n, 2];
%t A242785      h = 2^(Length@IntegerDigits[n, 2] - 1);
%t A242785      b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1,
%t A242785      If[t == m && r == 0, 0,
%t A242785           Sum[b[u - j, o + j - 1, Mod[2t, h]], {j, 1, u}]] +
%t A242785      If[t == m && r == 1, 0,
%t A242785           Sum[b[u + j - 1, o - j, Mod[2t+1, h]], {j, 1, o}]]];
%t A242785      b[n, 0, 0]];
%t A242785 a /@ Range[0, 30] (* _Jean-François Alcover_, Mar 23 2021, after _Alois P. Heinz_ *)
%Y A242785 Column k=0 of A242783.
%Y A242785 Main diagonal of A242784.
%Y A242785 Cf. A335308.
%K A242785 nonn
%O A242785 0,3
%A A242785 _Alois P. Heinz_, May 22 2014