A187256 -id:A187256 - 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 *)

A114848 Triangle read by rows T(n,k) = the number of Dyck paths of semilength n with k UUDDU's, 0<=k<=[(n-1)/2].

Original entry on oeis.org

1, 1, 2, 4, 1, 10, 4, 28, 13, 1, 82, 44, 6, 248, 153, 27, 1, 770, 536, 116, 8, 2440, 1889, 486, 46, 1, 7858, 6696, 1992, 240, 10, 25644, 23849, 8042, 1180, 70, 1, 84618, 85276, 32124, 5552, 430, 12, 281844, 305933, 127287, 25306, 2430, 99, 1, 946338, 1100692

Offset: 0

I. Tasoulas (jtas(AT)unipi.gr), Feb 20 2006

Row sums are Catalan numbers A000108.

			T(4,1) = 4 because there exist 4 Dyck paths with one occurrence of UUDDU : UDUUDDUD, UUDDUDUD, UUDDUUDD, UUUDDUDD.
Triangle begins:
:  0 :     1;
:  1 :     1;
:  2 :     2;
:  3 :     4,     1;
:  4 :    10,     4;
:  5 :    28,    13,     1;
:  6 :    82,    44,     6;
:  7 :   248,   153,    27,    1;
:  8 :   770,   536,   116,    8;
:  9 :  2440,  1889,   486,   46,   1;
: 10 :  7858,  6696,  1992,  240,  10;
: 11 : 25644, 23849,  8042, 1180,  70,  1;
: 12 : 84618, 85276, 32124, 5552, 430, 12;

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. - From _N. J. A. Sloane_, May 05 2012

Cf. A187256, A243752.

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, 3, 3, 2, 2][t])
      *`if`(t=5, z, 1) +b(x-1, y-1, [1, 1, 4, 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, Jun 10 2014

For[n = 1, n <= 20, n++, For[k = 0, k <= Floor[(n - 1)/2], k++, Print[Sum[(-1)^j * Binomial[n - 1 - (j + k), j + k] * Binomial[j + k, k] * Binomial[2(n - 2(j + k)), n - 2(j + k)]/(n - 2(j + k) + 1), {j, 0, Floor[(n - 1)/2] - k}]]]]

T(n,k) = Sum((-1)^j * binomial(n-1-(j+k), j+k) * binomial(j + k, k) * A000108(n-2(j+k)), j=0..[(n-1)/2]-k).

G.f. G = G(t,z) satisfies G = C(z/(z^2(1-t)+1)), where C(z) is g.f. of Catalan numbers.

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