A243753 Number A(n,k) of Dyck paths of semilength n avoiding the consecutive step pattern given by the binary expansion of k, where 1=U=(1,1) and 0=D=(1,-1); square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 2, 1, 1, 0, 0, 0, 1, 1, 2, 1, 4, 1, 1, 0, 0, 0, 1, 1, 2, 4, 1, 9, 1, 1, 0, 0, 0, 1, 1, 2, 4, 9, 1, 21, 1, 1, 0, 0, 0, 1, 1, 1, 4, 9, 21, 1, 51, 1, 1, 0, 0, 0

Offset

0,40

Links

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Example

Square array A(n,k) begins:
  1, 1, 1, 1, 1,   1, 1,   1,   1,    1, ...
  0, 0, 0, 1, 1,   1, 1,   1,   1,    1, ...
  0, 0, 0, 1, 1,   1, 1,   2,   2,    2, ...
  0, 0, 0, 1, 1,   2, 1,   4,   4,    4, ...
  0, 0, 0, 1, 1,   4, 1,   9,   9,    9, ...
  0, 0, 0, 1, 1,   9, 1,  21,  21,   23, ...
  0, 0, 0, 1, 1,  21, 1,  51,  51,   63, ...
  0, 0, 0, 1, 1,  51, 1, 127, 127,  178, ...
  0, 0, 0, 1, 1, 127, 1, 323, 323,  514, ...
  0, 0, 0, 1, 1, 323, 1, 835, 835, 1515, ...

Maple

A:= proc(n, k) option remember; local b, m, r, h;
      if k<2 then return `if`(n=0, 1, 0) fi;
      m:= iquo(k, 2, 'r'); h:= 2^ilog2(k); b:=
      proc(x, y, t) option remember; `if`(y<0 or y>x, 0, `if`(x=0, 1,
        `if`(t=m and r=1, 0, b(x-1, y+1, irem(2*t+1, h)))+
        `if`(t=m and r=0, 0, b(x-1, y-1, irem(2*t, h)))))
      end; forget(b);
      b(2*n, 0, 0)
    end:
seq(seq(A(n, d-n), n=0..d), d=0..14);

Mathematica

A[n_, k_] := A[n, k] = Module[{b, m, r, h}, If[k<2, Return[If[n == 0, 1, 0]]]; {m, r} = QuotientRemainder[k, 2]; h = 2^Floor[Log[2, k]]; b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x == 0, 1, If[t == m && r == 1, 0, b[x-1, y+1, Mod[2*t+1, h]]] + If[t == m && r == 0, 0, b[x-1, y-1, Mod[2*t, h]]]]]; b[2*n, 0, 0]]; Table[ Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Jan 27 2015, after Alois P. Heinz *)

Crossrefs

Columns give: 0, 1, 2: A000007, 3, 4, 6: A000012, 5: A001006(n-1) for n>0, 7, 8, 14: A001006, 9: A135307, 10: A078481 for n>0, 11, 13: A105633(n-1) for n>0, 12: A082582, 15, 16: A036765, 19, 27: A114465, 20, 24, 26: A157003, 21: A247333, 25: A187256(n-1) for n>0.

Main diagonal gives A243754 or column k=0 of A243752.

Cf. A242450, A243827, A243828, A243829, A243830, A243831, A243832, A243833, A243834, A243835, A243836.

Sequence in context: A354841 A339772 A250211 * A219238 A025918 A030425

Adjacent sequences: A243750 A243751 A243752 * A243754 A243755 A243756

Keyword

nonn,tabl

Author

Alois P. Heinz, Jun 09 2014

Status

approved