cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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.

This page as a plain text file.
%I A242784 #30 Sep 13 2020 14:40:58
%S A242784 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 A242784 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 A242784 450,2017,128,1,1,1,1,2,6,23,90,331,2619,13358,256,1,1
%N 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.
%H A242784 Alois P. Heinz, <a href="/A242784/b242784.txt">Antidiagonals n = 0..140, flattened</a>
%e A242784 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 A242784 Square array A(n,k) begins:
%e A242784   1, 1,   1,     1,     1,     1,     1,     1,     1, ...
%e A242784   1, 1,   1,     1,     1,     1,     1,     1,     1, ...
%e A242784   1, 1,   2,     2,     2,     2,     2,     2,     2, ...
%e A242784   1, 1,   4,     5,     6,     6,     6,     6,     6, ...
%e A242784   1, 1,   8,    17,    21,    19,    21,    23,    24, ...
%e A242784   1, 1,  16,    70,    90,    70,    90,   111,   116, ...
%e A242784   1, 1,  32,   349,   450,   331,   450,   642,   672, ...
%e A242784   1, 1,  64,  2017,  2619,  1863,  2619,  4326,  4536, ...
%e A242784   1, 1, 128, 13358, 17334, 11637, 17334, 33333, 34944, ...
%p A242784 A:= proc(n, k) option remember; local b, m, r, h;
%p A242784       if k<2 then return 1 fi;
%p A242784       m:= iquo(k, 2, 'r'); h:= 2^ilog2(k);
%p A242784       b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
%p A242784       `if`(t=m and r=0, 0, add(b(u-j, o+j-1, irem(2*t, h)), j=1..u))+
%p A242784       `if`(t=m and r=1, 0, add(b(u+j-1, o-j, irem(2*t+1, h)), j=1..o)))
%p A242784       end; forget(b);
%p A242784       b(n, 0, 0)
%p A242784     end:
%p A242784 seq(seq(A(n, d-n), n=0..d), d=0..15);
%t A242784 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 A242784 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 A242784 Main diagonal gives A242785.
%Y A242784 Cf. A242783, A335308.
%K A242784 nonn,tabl
%O A242784 0,13
%A A242784 _Alois P. Heinz_, May 22 2014