A135307 -id:A135307 - cp's OEIS frontend

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

Alois P. Heinz, Jun 09 2014

			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, ...

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

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.

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 *)

A135306 Triangle read by rows: T(n,k) = the number of Dyck paths of semilength n with k UDDU's.

Original entry on oeis.org

1, 1, 2, 4, 1, 9, 5, 23, 17, 2, 63, 54, 15, 178, 177, 69, 5, 514, 594, 273, 49, 1515, 1997, 1056, 280, 14, 4545, 6698, 4077, 1308, 168, 13827, 22487, 15545, 5745, 1140, 42, 42540, 75701, 58377, 24695, 6105, 594, 132124, 255455, 216864, 103862, 29810

Offset: 0

N. J. A. Sloane, Dec 07 2007

From Emeric Deutsch, Dec 15 2007: (Start)
Row 0 has 1 term; row n (n >= 1) has ceiling(n/2) terms.
Row sums yield the Catalan numbers (A000108).
Column 0 yields A135307.
T(2n+1, n) = binomial(2n,n)/(n+1) (the Catalan numbers, A000108). (End)

			Triangle begins:
     1;
     1;
     2;
     4,    1;
     9,    5;
    23,   17,    2;
    63,   54,   15;
   178,  177,   69,    5;
   514,  594,  273,   49;
  1515, 1997, 1056,  280,   14;
  4545, 6698, 4077, 1308,  168;
  ...
T(4,1) = 5 because we have U(UDDU)DUD, U(UDDU)UDD, UU(UDDU)DD, UDU(UDDU)D and UUD(UDDU)D (the UDDU's are shown between parentheses).

Alois P. Heinz, Rows n = 0..200, flattened
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Cf. A000108, A135307, A243752.

A135306 := proc(n,k) if n =0 then 1 ; else add((-1)^(j-k)*binomial(n-k,j-k)*binomial(2*n-3*j,n-j+1),j=k..floor((n-1)/2)) ; %*binomial(n,k)/n ; fi ; end: for n from 0 to 20 do for k from 0 to max(0,(n-1)/2) do printf("%a, ",A135306(n,k)) ; od: od: # R. J. Mathar, Dec 08 2007
T:=proc(n,k) options operator, arrow: binomial(n,k)*(sum((-1)^(j-k)*binomial(n-k,j-k)*binomial(2*n-3*j,n-j+1),j=k..floor((1/2)*n-1/2)))/n end proc: 1; for n to 13 do seq(T(n,k),k=0..ceil((n-2)*1/2)) end do; # yields sequence in triangular form; Emeric Deutsch, Dec 15 2007

T[n_, k_] := Binomial[n, k]*Sum[(-1)^(j-k)*Binomial[n-k, j-k]*Binomial[2*n - 3*j, -j+n+1], {j, k, (n-1)/2}]/n; T[0, 0] = 1; Table[T[n, k], {n, 0, 13}, {k, 0, If[n == 0, 0, Quotient[n-1, 2]]}] // Flatten (* Jean-François Alcover, Nov 27 2014, after Emeric Deutsch *)

From Emeric Deutsch, Dec 15 2007: (Start)
T(n,k) = (1/n)*binomial(n,k)*Sum_{j=k..floor((n-1)/2)} (-1)^(j-k)*binomial(n-k, j-k)*binomial(2n-3j, n-j+1).
G.f.: G = G(t,z) satisfies z*G^3 - ((1-t)*z+1)*G^2 + (1+2*(1-t)*z)*G - (1-t)*z = 0. (End)

More terms from R. J. Mathar and Emeric Deutsch, Dec 08 2007

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica