|
| |
|
|
A242784
|
|
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.
|
|
57
|
|
|
|
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, 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, 450, 2017, 128, 1, 1, 1, 1, 2, 6, 23, 90, 331, 2619, 13358, 256, 1, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,13
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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).
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 2, 2, 2, 2, 2, 2, 2, ...
1, 1, 4, 5, 6, 6, 6, 6, 6, ...
1, 1, 8, 17, 21, 19, 21, 23, 24, ...
1, 1, 16, 70, 90, 70, 90, 111, 116, ...
1, 1, 32, 349, 450, 331, 450, 642, 672, ...
1, 1, 64, 2017, 2619, 1863, 2619, 4326, 4536, ...
1, 1, 128, 13358, 17334, 11637, 17334, 33333, 34944, ...
|
|
|
MAPLE
|
A:= proc(n, k) option remember; local b, m, r, h;
if k<2 then return 1 fi;
m:= iquo(k, 2, 'r'); h:= 2^ilog2(k);
b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
`if`(t=m and r=0, 0, add(b(u-j, o+j-1, irem(2*t, h)), j=1..u))+
`if`(t=m and r=1, 0, add(b(u+j-1, o-j, irem(2*t+1, h)), j=1..o)))
end; forget(b);
b(n, 0, 0)
end:
seq(seq(A(n, d-n), n=0..d), d=0..15);
|
|
|
MATHEMATICA
|
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 *)
|
|
|
CROSSREFS
|
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.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
