|
%I #30 Sep 13 2020 14:40:58
%S 1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,2,4,1,1,1,1,2,5,8,1,1,1,1,2,6,17,
%T 16,1,1,1,1,2,6,21,70,32,1,1,1,1,2,6,19,90,349,64,1,1,1,1,2,6,21,70,
%U 450,2017,128,1,1,1,1,2,6,23,90,331,2619,13358,256,1,1
%N Number A(n,k) of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of k, where 1=up and 0=down; square array A(n,k), n>=0, k>=0, read by antidiagonals.
%H Alois P. Heinz, <a href="/A242784/b242784.txt">Antidiagonals n = 0..140, flattened</a>
%e A(4,5) = 19 because there are 4! = 24 permutations of {1,2,3,4} and only 5 of them do not avoid the consecutive step pattern up, down, up given by the binary expansion of 5 = 101_2: (1,3,2,4), (1,4,2,3), (2,3,1,4), (2,4,1,3), (3,4,1,2).
%e Square array A(n,k) begins:
%e 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 1, 1, 2, 2, 2, 2, 2, 2, 2, ...
%e 1, 1, 4, 5, 6, 6, 6, 6, 6, ...
%e 1, 1, 8, 17, 21, 19, 21, 23, 24, ...
%e 1, 1, 16, 70, 90, 70, 90, 111, 116, ...
%e 1, 1, 32, 349, 450, 331, 450, 642, 672, ...
%e 1, 1, 64, 2017, 2619, 1863, 2619, 4326, 4536, ...
%e 1, 1, 128, 13358, 17334, 11637, 17334, 33333, 34944, ...
%p A:= proc(n, k) option remember; local b, m, r, h;
%p if k<2 then return 1 fi;
%p m:= iquo(k, 2, 'r'); h:= 2^ilog2(k);
%p b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
%p `if`(t=m and r=0, 0, add(b(u-j, o+j-1, irem(2*t, h)), j=1..u))+
%p `if`(t=m and r=1, 0, add(b(u+j-1, o-j, irem(2*t+1, h)), j=1..o)))
%p end; forget(b);
%p b(n, 0, 0)
%p end:
%p seq(seq(A(n, d-n), n=0..d), d=0..15);
%t Clear[A]; A[n_, k_] := A[n, k] = Module[{b, m, r, h}, If[k < 2, Return[1]]; {m, r} = QuotientRemainder[k, 2]; h = 2^Floor[Log[2, k]]; b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, If[t == m && r == 0, 0, Sum[b[u - j, o + j - 1, Mod[2*t, h]], {j, 1, u}]] + If[t == m && r == 1, 0, Sum[b[u + j - 1, o - j, Mod[2*t + 1, h]], {j, 1, o}]]]; b[n, 0, 0]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 15}] // Flatten (* _Jean-François Alcover_, Sep 22 2014, translated from Maple *)
%Y Columns give: 0, 1: A000012, 2: A011782, 3: A049774, 4, 6: A177479, 5: A177477, 7: A117158, 8, 14: A177518, 9: A177519, 10: A177520, 11, 13: A177521, 12: A177522, 15: A177523, 16, 30: A177524, 17: A177525, 18, 22: A177526, 19, 25: A177527, 20, 26: A177528, 21: A177529, 23, 29: A177530, 24, 28: A177531, 27: A177532, 31: A177533, 32, 62: A177534, 33: A177535, 34, 46: A177536, 35, 49: A177537, 36, 54: A177538, 37, 41: A177539, 38: A177540, 39, 57: A177541, 40, 58: A177542, 42: A177543, 43, 53: A177544, 44, 50: A177545, 45: A177546, 47, 61: A177547, 48, 60: A177548, 51: A177549, 52: A177550, 55, 59: A177551, 56: A177552, 63: A177553, 127: A230051, 255: A230231, 511: A230232, 1023: A230233, 2047: A254523.
%Y Main diagonal gives A242785.
%Y Cf. A242783, A335308.
%K nonn,tabl
%O 0,13
%A _Alois P. Heinz_, May 22 2014
|
