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 *)
A246188
Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k occurrences of the string ududu, where u=(1,1), d=(1,-1).
Original entry on oeis.org
1, 1, 2, 4, 1, 11, 2, 1, 31, 8, 2, 1, 92, 28, 9, 2, 1, 283, 99, 34, 10, 2, 1, 893, 354, 129, 40, 11, 2, 1, 2875, 1273, 492, 161, 46, 12, 2, 1, 9407, 4598, 1882, 646, 195, 52, 13, 2, 1, 31189, 16679, 7199, 2597, 816, 231, 58, 14, 2, 1, 104555, 60712, 27570, 10400, 3422, 1002, 269, 64, 15, 2, 1
Offset: 0
Row 4 is 11, 2, 1; indeed in the 14 Dyck paths of semilength 4 ududu occurs only once in ududuudd, once in uudududd, and twice in udududud.
Triangle starts:
1;
1;
2;
4, 1;
11, 2, 1;
31, 8, 2, 1;
...
-
C := proc (u) options operator, arrow: (1/2-(1/2)*sqrt(1-4*u))/u end proc: G := C(z*(1-t*z-z^2+t*z^2)/(1-t*z-z^3+t*z^3)): Gser := simplify(series(G, z = 0, 20)): T := proc (n, k) options operator, arrow: coeff(coeff(Gser, z, n), t, k) end proc: 1; 1; for n from 2 to 12 do seq(T(n, k), k = 0 .. n-2) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
`if`(x=0, 1, expand(b(x-1, y+1, [2, 2, 4, 2, 4][t])*
`if`(t=5, z, 1) +b(x-1, y-1, [1, 3, 1, 5, 1][t]))))
end:
T:= n->(p->seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..15); # Alois P. Heinz, Sep 10 2014
-
b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x == 0, 1, Expand[b[x-1, y+1, {2, 2, 4, 2, 4}[[t]] ]*If[t == 5, z, 1] + b[x-1, y-1, {1, 3, 1, 5, 1}[[t]] ]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 1]];Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, May 27 2015, after Alois P. Heinz *)
Showing 1-2 of 2 results.
Comments