A243752
Number T(n,k) of Dyck paths of semilength n having exactly k (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=U=(1,1) and 0=D=(1,-1); triangle T(n,k), n>=0, read by rows.
Original entry on oeis.org
1, 0, 1, 0, 1, 1, 1, 3, 1, 1, 11, 2, 9, 16, 12, 4, 1, 1, 57, 69, 5, 127, 161, 98, 35, 7, 1, 323, 927, 180, 1515, 1997, 1056, 280, 14, 4191, 5539, 3967, 1991, 781, 244, 64, 17, 1, 1, 10455, 25638, 18357, 4115, 220, 1, 20705, 68850, 77685, 34840, 5685, 246, 1
Offset: 0
Triangle T(n,k) begins:
: n\k : 0 1 2 3 4 5 ...
+-----+----------------------------------------------------------
: 0 : 1; [row 0 of A131427]
: 1 : 0, 1; [row 1 of A131427]
: 2 : 0, 1, 1; [row 2 of A090181]
: 3 : 1, 3, 1; [row 3 of A001263]
: 4 : 1, 11, 2; [row 4 of A091156]
: 5 : 9, 16, 12, 4, 1; [row 5 of A091869]
: 6 : 1, 57, 69, 5; [row 6 of A091156]
: 7 : 127, 161, 98, 35, 7, 1; [row 7 of A092107]
: 8 : 323, 927, 180; [row 8 of A091958]
: 9 : 1515, 1997, 1056, 280, 14; [row 9 of A135306]
: 10 : 4191, 5539, 3967, 1991, 781, 244, ... [row 10 of A094507]
Columns k=0-10 give:
A243754,
A243770,
A243771,
A243772,
A243773,
A243774,
A243775,
A243776,
A243777,
A243778,
A243779, or main diagonals of
A243753,
A243827,
A243828,
A243829,
A243830,
A243831,
A243832,
A243833,
A243834,
A243835,
A243836.
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.
Original entry on oeis.org
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
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, ...
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.
Cf.
A242450,
A243827,
A243828,
A243829,
A243830,
A243831,
A243832,
A243833,
A243834,
A243835,
A243836.
-
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);
-
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 *)
Showing 1-2 of 2 results.