A244236 -id:A244236 - cp's OEIS frontend

A243827 Number A(n,k) of Dyck paths of semilength n having exactly one occurrence of 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.

0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 3, 1, 0, 0, 0, 0, 1, 4, 6, 1, 0, 0, 0, 0, 1, 2, 11, 10, 1, 0, 0, 0, 0, 0, 4, 6, 26, 15, 1, 0, 0, 0, 0, 0, 1, 11, 16, 57, 21, 1, 0, 0, 0, 0, 0, 1, 4, 26, 45, 120, 28, 1, 0, 0, 0, 0, 1, 1, 5, 15, 57, 126, 247, 36, 1, 0, 0

Offset: 0

Alois P. Heinz, Jun 11 2014

			Square array A(n,k) begins:
  0, 0, 0,  0,   0,    0,   0,    0,    0,    0, ...
  1, 1, 1,  0,   0,    0,   0,    0,    0,    0, ...
  0, 0, 1,  1,   1,    1,   1,    0,    0,    0, ...
  0, 0, 1,  3,   4,    2,   4,    1,    1,    1, ...
  0, 0, 1,  6,  11,    6,  11,    4,    5,    5, ...
  0, 0, 1, 10,  26,   16,  26,   15,   21,   17, ...
  0, 0, 1, 15,  57,   45,  57,   50,   78,   54, ...
  0, 0, 1, 21, 120,  126, 120,  161,  274,  177, ...
  0, 0, 1, 28, 247,  357, 247,  504,  927,  594, ...
  0, 0, 1, 36, 502, 1016, 502, 1554, 3061, 1997, ...

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

Columns k=2-10 give: A000012(n) for n>0, A000217(n-1) for n>0, A000295(n-1) for n>0, A005717(n-1) for n>1, A000295(n-1) for n>0, A014532(n-2) for n>2, A108863, A244235, A244236.
Main diagonal gives A243770 or column k=1 of A243752.
Cf. A243753, A243828, A243829, A243830, A243831, A243832, A243833, A243834, A243835, A243836.

A094507 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n and having k UDUD's (here U=(1,1), D=(1,-1)).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 5, 1, 1, 19, 14, 7, 1, 1, 53, 46, 22, 9, 1, 1, 153, 150, 82, 31, 11, 1, 1, 453, 495, 299, 127, 41, 13, 1, 1, 1367, 1651, 1087, 507, 181, 52, 15, 1, 1, 4191, 5539, 3967, 1991, 781, 244, 64, 17, 1, 1, 13015, 18692, 14442, 7824, 3271, 1128, 316, 77, 19

Offset: 0

Emeric Deutsch, Jun 05 2004

Column k=0 is A078481.
Column k=1 is A244236.
Row sums are the Catalan numbers (A000108).

			T(3,0) = 3 because UDUUDD, UUDDUD and UUUDDD are the only Dyck paths of semilength 3 and having no UDUD in them.
Triangle begins:
     1;
     1;
     1,    1;
     3,    1,    1;
     7,    5,    1,    1;
    19,   14,    7,    1,   1;
    53,   46,   22,    9,   1,   1;
   153,  150,   82,   31,  11,   1,  1;
   453,  495,  299,  127,  41,  13,  1,  1;
  1367, 1651, 1087,  507, 181,  52, 15,  1, 1;
  4191, 5539, 3967, 1991, 781, 244, 64, 17, 1, 1;

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

Cf. A078481, A000108, A102405 (the same for DUDU), A243752, A243753, A244236.

T(2n,n) gives A304361.

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][t])
      +b(x-1, y-1, [1, 3, 1, 3][t])*`if`(t=4, z, 1))))
    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 02 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}[[t]]] + b[x-1, y-1, {1, 3, 1, 3}[[t]]]*If[t == 4, z, 1]]]]; 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, Apr 29 2015, after Alois P. Heinz *)

G.f.: G=G(t, z) satisfies the equation z(1+z-tz)G^2-(1+z+z^2-tz-tz^2)G+1+z-tz=0.

cp's OEIS Frontend

A243827 Number A(n,k) of Dyck paths of semilength n having exactly one occurrence of 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

A094507 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n and having k UDUD's (here U=(1,1), D=(1,-1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula