A243752 -id:A243752 - cp's OEIS frontend

A243833 Number A(n,k) of Dyck paths of semilength n having exactly seven (possibly overlapping) occurrences 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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 429, 0, 0, 0, 0, 0, 0, 0, 429, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 336, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36, 2520, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 540, 13860, 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,  0, ...
    0,   0,    0,   0, 0,  0, 0,  0, 0, 0,  0, ...
    0,   0,    0,   0, 0,  0, 0,  0, 0, 0,  0, ...
    0,   0,    0,   0, 0,  0, 0,  0, 0, 0,  0, ...
    0,   0,    0,   0, 0,  0, 0,  0, 0, 0,  0, ...
    0,   0,    0,   0, 0,  0, 0,  0, 0, 0,  0, ...
    0,   0,    0,   0, 0,  0, 0,  0, 0, 0,  0, ...
  429, 429,    1,   0, 0,  0, 0,  0, 0, 0,  0, ...
    0,   0,   28,   1, 0,  1, 0,  0, 0, 0,  1, ...
    0,   0,  336,  36, 0,  8, 0,  1, 0, 0,  1, ...
    0,   0, 2520, 540, 0, 72, 0, 10, 0, 0, 17, ...

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

Main diagonal gives A243776 or column k=7 of A243752.

Cf. A243753, A243827, A243828, A243829, A243830, A243831, A243832, A243834, A243835, A243836.

A243834 Number A(n,k) of Dyck paths of semilength n having exactly eight (possibly overlapping) occurrences 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.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1430, 0, 0, 0, 0, 0, 0, 0, 0, 1430, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 540, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 45, 4950, 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,  0, 0, ...
     0,    0,    0,   0, 0,  0, 0,  0, 0, 0,  0, 0, ...
     0,    0,    0,   0, 0,  0, 0,  0, 0, 0,  0, 0, ...
     0,    0,    0,   0, 0,  0, 0,  0, 0, 0,  0, 0, ...
     0,    0,    0,   0, 0,  0, 0,  0, 0, 0,  0, 0, ...
     0,    0,    0,   0, 0,  0, 0,  0, 0, 0,  0, 0, ...
     0,    0,    0,   0, 0,  0, 0,  0, 0, 0,  0, 0, ...
     0,    0,    0,   0, 0,  0, 0,  0, 0, 0,  0, 0, ...
  1430, 1430,    1,   0, 0,  0, 0,  0, 0, 0,  0, 0, ...
     0,    0,   36,   1, 0,  1, 0,  0, 0, 0,  1, 0, ...
     0,    0,  540,  45, 0,  9, 0,  1, 0, 0,  1, 0, ...
     0,    0, 4950, 825, 0, 90, 0, 11, 0, 0, 19, 0, ...

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

Main diagonal gives A243777 or column k=8 of A243752.

Cf. A243753, A243827, A243828, A243829, A243830, A243831, A243832, A243833, A243835, A243836.

A243835 Number A(n,k) of Dyck paths of semilength n having exactly nine (possibly overlapping) occurrences 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.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4862, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4862, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 45, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 825, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 55, 9075, 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, 0, 0, ...
     0,    0,   0,  0, 0,  0, 0, 0, 0, 0, 0, 0, ...
     0,    0,   0,  0, 0,  0, 0, 0, 0, 0, 0, 0, ...
     0,    0,   0,  0, 0,  0, 0, 0, 0, 0, 0, 0, ...
     0,    0,   0,  0, 0,  0, 0, 0, 0, 0, 0, 0, ...
     0,    0,   0,  0, 0,  0, 0, 0, 0, 0, 0, 0, ...
     0,    0,   0,  0, 0,  0, 0, 0, 0, 0, 0, 0, ...
     0,    0,   0,  0, 0,  0, 0, 0, 0, 0, 0, 0, ...
     0,    0,   0,  0, 0,  0, 0, 0, 0, 0, 0, 0, ...
  4862, 4862,   1,  0, 0,  0, 0, 0, 0, 0, 0, 0, ...
     0,    0,  45,  1, 0,  1, 0, 0, 0, 0, 1, 0, ...
     0,    0, 825, 55, 0, 10, 0, 1, 0, 0, 1, 0, ...

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

Main diagonal gives A243778 or column k=9 of A243752.

Cf. A243753, A243827, A243828, A243829, A243830, A243831, A243832, A243833, A243834, A243836.

A243836 Number A(n,k) of Dyck paths of semilength n having exactly ten (possibly overlapping) occurrences 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.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16796, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16796, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 55, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1210, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 66, 15730, 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, 0, 0, ...
      0,     0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
      0,     0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
      0,     0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
      0,     0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
      0,     0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
      0,     0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
      0,     0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
      0,     0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
      0,     0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
  16796, 16796,  1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
      0,     0, 55, 1, 0, 1, 0, 0, 0, 0, 1, 0, ...

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

Main diagonal gives A243779 or column k=10 of A243752.

Cf. A243753, A243827, A243828, A243829, A243830, A243831, A243832, A243833, A243834, A243835.

A243881 Number T(n,k) of Dyck paths of semilength n having exactly k (possibly overlapping) occurrences of the consecutive steps UDUUUDDDUD (with U=(1,1), D=(1,-1)); triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/4)), read by rows.

Original entry on oeis.org

1, 1, 2, 5, 14, 41, 1, 129, 3, 419, 10, 1395, 35, 4737, 124, 1, 16338, 454, 4, 57086, 1684, 16, 201642, 6305, 65, 718855, 23781, 263, 1, 2583149, 90209, 1077, 5, 9346594, 343809, 4419, 23, 34023934, 1315499, 18132, 105, 124519805, 5050144, 74368, 472, 1

Offset: 0

Alois P. Heinz, Jun 13 2014

UDUUUDDDUD is the only Dyck path of semilength 5 that contains all eight consecutive step patterns of length 3.

			Triangle T(n,k) begins:
:  0 :        1;
:  1 :        1;
:  2 :        2;
:  3 :        5;
:  4 :       14;
:  5 :       41,       1;
:  6 :      129,       3;
:  7 :      419,      10;
:  8 :     1395,      35;
:  9 :     4737,     124,     1;
: 10 :    16338,     454,     4;
: 11 :    57086,    1684,    16;
: 12 :   201642,    6305,    65;
: 13 :   718855,   23781,   263,   1;
: 14 :  2583149,   90209,  1077,   5;
: 15 :  9346594,  343809,  4419,  23;
: 16 : 34023934, 1315499, 18132, 105;

Alois P. Heinz, Rows n = 0..300, flattened

Columns k=0-10 give: A243870, A243871, A243872, A243873, A243874, A243875, A243876, A243877, A243878, A243879, A243880.
Row sums give A000108.
T(738,k) = A243752(738,k).
T(n,0) = A243753(n,738).
Cf. A243882.

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, 5, 6, 2, 4, 2, 10, 2][t])+`if`(t=10,
      z, 1)*b(x-1, y-1, [1, 3, 1, 3, 3, 7, 8, 9, 1, 3][t]))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..20);

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, 5, 6, 2, 4, 2, 10, 2}[[t]]] + If[t==10, z, 1]*b[x-1, y-1, {1, 3, 1, 3, 3, 7, 8, 9, 1, 3}[[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, 20}] // Flatten (* Jean-François Alcover, Mar 31 2015, after Alois P. Heinz *)

A091869 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k peaks at even height.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 4, 6, 3, 1, 9, 16, 12, 4, 1, 21, 45, 40, 20, 5, 1, 51, 126, 135, 80, 30, 6, 1, 127, 357, 441, 315, 140, 42, 7, 1, 323, 1016, 1428, 1176, 630, 224, 56, 8, 1, 835, 2907, 4572, 4284, 2646, 1134, 336, 72, 9, 1, 2188, 8350, 14535, 15240, 10710, 5292, 1890, 480, 90, 10, 1

Offset: 1

Emeric Deutsch, Mar 10 2004

Number of ordered trees with n edges having k leaves at even height. Row sums are the Catalan numbers (A000108). T(n,0)=A001006(n-1) (the Motzkin numbers). Sum_{k=0..n-1} k*T(n,k) = binomial(2n-2, n-2) = A001791(n-1). Mirror image of A091187.
T(n,k) is the number of Dyck paths of semilength n and having k dud's (here u=(1,1) and d=(1,-1)). Example: T(4,2)=3 because we have uud(du[d)ud], uu(dud)(dud) and uu(du[d)ud]d (the dud's are shown between parentheses).
T(n,k) is the number of Dyck paths of semilength n and containing exactly k double rises whose matching down steps form a doublefall. Example: UUUDUDDD has 2 double rises but only the first has matching Ds - the path's last 2 steps - forming a doublefall. (Travel horizontally east from an up step to encounter its matching down step.) - David Callan, Jul 15 2004
T(n,k) is the number of ordered trees on n edges containing k edges of outdegree 1. (The outdegree of an edge is the outdegree of its child vertex. Thus edges of outdegree 1 correspond to non-root vertices of outdegree 1.) T(3,2)=2 because
  /\.../\.
  |.....|.
each have one edge of outdegree 1. - David Callan, Oct 25 2004
Exponential Riordan array [exp(x)*Bessel_I(1,2x)/x, x]. - Paul Barry, Mar 09 2010
T(n, k) is the number of Dyck paths of semilength n and having k udu's (here u=(1,1) and d=(1,-1)). Note that reversing a path swaps u and d, thus udu becomes dud and vice versa. - Michael Somos, Feb 26 2020

			T(4,1)=6 because we have u(ud)dudud, udu(ud)dud, ududu(ud)d, uuudd(ud)d, u(ud)uuddd and uuu(ud)ddd (here u=(1,1), d=(1,-1) and the peaks at even height are shown between parentheses).
Triangle begins:
    1;
    1,    1;
    2,    2,    1;
    4,    6,    3,    1;
    9,   16,   12,    4,    1;
   21,   45,   40,   20,    5,    1;
   51,  126,  135,   80,   30,    6,   1;
  127,  357,  441,  315,  140,   42,   7,  1;
  323, 1016, 1428, 1176,  630,  224,  56,  8, 1;
  835, 2907, 4572, 4284, 2646, 1134, 336, 72, 9, 1;
  ...

Alois P. Heinz, Rows n = 1..200, flattened
J. L. Baril and S. Kirgizov, The pure descent statistic on permutations, Preprint, 2016. See Table 2.
David Callan, Bijections for Dyck paths with all peak heights of the same parity, arXiv:1702.06150 [math.CO], 2017.
M. Dziemianczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 9-24.
Sergi Elizalde, Johnny Rivera Jr., and Yan Zhuang, Counting pattern-avoiding permutations by big descents, arXiv:2408.15111 [math.CO], 2024. See p. 11.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
Yidong Sun, The statistic "number of udu's" in Dyck paths, Discrete Math., 287 (2004), 177-186.
Chao-Jen Wang, Applications of the Goulden-Jackson cluster method to counting Dyck paths by occurrences of subwords.

Cf. A001006, A005717, A102839, A371408, A375253, A375259.
Cf. A000108, A001791, A091187, A243752.
T(2n,n) gives A371411.

T := proc(n,k) if k0, b(x-1, y-1, 0)*z^irem(t*y+t, 2), 0)+
      `if`(y (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):
seq(T(n), n=1..16);  # Alois P. Heinz, May 12 2017

(* m = MotzkinNumber *) m[0] = 1; m[n_] := m[n] = m[n - 1] + Sum[m[k]*m[n - 2 - k], {k, 0, n - 2}]; t[n_, n_] = 1; t[n_, k_] := m[n - k]*Binomial[n - 1, k - 1]; Table[t[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 10 2013 *)

{T(n, k) = my(y, c, w); if( k<0 || k>=n, 0, w = vector(n);   forvec(v=vector(2*n, k, [0, 1]), c=y=0; for(k=1, 2*n, if( 0>(y += (-1)^v[k]), break)); if( y, next); for(i=1, 2*n-2, c += ([0, 1, 0] == v[i..i+2])); w[c+1]++); w[k+1])}; /* Michael Somos, Feb 26 2020 */

T(n, k) = binomial(n-1, k)*(Sum_{j=0..ceiling((n-k)/2)} binomial(n-k, j)*binomial(n-k-j, j-1))/(n-k) for 0 <= k < n; T(n, k)=0 for k >= n.
G.f.: G = G(t, z) satisfies z*G^2 - (1 + z - t*z)*G + 1 + z - t*z = 0.
T(n, k) = M(n-k-1)*binomial(n-1, k), where M(n) = A001006(n) are the Motzkin numbers.
T(n+1, k+1) = n*T(n, k)/(k+1). - David Callan, Dec 09 2004
G.f.: 1/(1-x-xy-x^2/(1-x-xy-x^2/(1-x-xy-x^2/(1-x-xy-x^2/(1-... (continued fraction). - Paul Barry, Aug 03 2009
E.g.f.: exp(x+xy)*Bessel_I(1,2x)/x. - Paul Barry, Mar 10 2010

A131427 A000108(n) preceded by n zeros.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 0, 0, 0, 5, 0, 0, 0, 0, 14, 0, 0, 0, 0, 0, 42, 0, 0, 0, 0, 0, 0, 132, 0, 0, 0, 0, 0, 0, 0, 429, 0, 0, 0, 0, 0, 0, 0, 0, 1430, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4862, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16796, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 58786, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 208012

Offset: 0

Gary W. Adamson, Jul 10 2007

Triangle given by A000004 DELTA A000012 where DELTA is the operator defined in A084938. - Philippe Deléham, Jul 12 2007

T(n,k) is the number of Dyck paths of semilength n having exactly k U=(1,1) steps. - Alois P. Heinz, Jun 09 2014

			First few rows of the triangle are:
1;
0, 1;
0, 0, 2;
0, 0, 0, 5;
0, 0, 0, 0, 14;
0, 0, 0, 0, 0, 42;
...

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

Cf. A131428, A131429, A000108, A243752.

T:= (n, k)-> `if`(kAlois P. Heinz, Jun 09 2014

T[n_, n_] := CatalanNumber[n]; T[, ] = 0;
Table[T[n, k], {n, 0, 15}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 20 2016 *)

A000108(n) preceded by n zeros, as an infinite lower triangular matrix.

More terms from Philippe Deléham, Oct 16 2008

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.

A091156 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having k long ascents (i.e., ascents of length at least 2). Rows are of length 1,1,2,2,3,3,... .

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 11, 2, 1, 26, 15, 1, 57, 69, 5, 1, 120, 252, 56, 1, 247, 804, 364, 14, 1, 502, 2349, 1800, 210, 1, 1013, 6455, 7515, 1770, 42, 1, 2036, 16962, 27940, 11055, 792, 1, 4083, 43086, 95458, 57035, 8217, 132, 1, 8178, 106587, 305812, 257257

Offset: 0

Emeric Deutsch, Feb 22 2004

Also number of ordered trees with n edges, having k branch nodes (i.e., vertices of outdegree at least 2).
Also number of Łukasiewicz paths of length n having k fall steps (1,-1) that start at an odd level. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: T(4,2)=2 because we have U(D)U(D) and U(3)(D)D(D), where U=(1,1), D=(1,-1), U(3)=(1,3) and the fall steps that start at an odd level are shown between parentheses. Row n has 1+floor(n/2) terms. Row sums are the Catalan numbers (A000108). T(2n,n)=A000108(n). T(2n+1,n)=A001791(n+1)=binomial(2n+2,n). - Emeric Deutsch, Jan 06 2005
Also number of Dyck paths of semilength n with k UUD's - I. Tasoulas (jtas(AT)unipi.gr), Feb 19 2006
T(n,k) = number of Dyck n-paths whose decomposition into 2-step subpaths contains k UUs. For example, T(4,2)=2 counts UU|UU|DD|DD, UU|DD|UU|DD (vertical bars indicate path decomposition). - David Callan, Jun 07 2006
T(n,k) = number of binary trees on n-1 edges containing k right edges whose child vertex has no right child. Under Knuth's "natural" correspondence, such a vertex in binary (n-1)-tree ~ a vertex of outdegree >=2 in ordered n-tree. - David Callan, Sep 25 2006
T(n,k) = number of binary trees on n-1 edges containing k left edges whose child vertex has no left child. Under "natural" correspondence, such a vertex in binary (n-1)-tree ~ a leaf edge with no left neighbor edge and not incident to the root in ordered n-tree ~ a UUD in Dyck n-path. - David Callan, Sep 25 2006
T(n,k) = number of permutations of length n avoiding 321 (classically) with k descents. - Andrew Baxter, May 17 2011.

			T(4,1) = 11 because among the 14 Dyck paths of semilength 4, the paths that do not have exactly one long ascent are UDUDUDUD (no long ascent), UUDDUUDD (two long ascents) and UUDUUDDD (two long ascents). Here U=(1,1) and D=(1,-1).
Triangle begins:
  1;
  1;
  1,    1;
  1,    4;
  1,   11,    2;
  1,   26,   15;
  1,   57,   69,    5;
  1,  120,  252,   56;
  1,  247,  804,  364,   14;
  1,  502, 2349, 1800,  210;
  1, 1013, 6455, 7515, 1770, 42;
  ...

R. P. Stanley, Enumerative Combinatorics, Vol. 1, 1986; See Exercise 3.71(f).

Alois P. Heinz, Rows n = 0..200, flattened
M. Barnabei et al., The descent statistic over 123-avoiding permutations, arXiv:0910.0963 [math.CO], 2009.
A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011. See p. 88.
Michael Bukata, Ryan Kulwicki, Nicholas Lewandowski, Lara Pudwell, Jacob Roth, Teresa Wheeland, Distributions of Statistics over Pattern-Avoiding Permutations, arXiv:1812.07112 [math.CO], 2018.
Colin Defant, Stack-Sorting Preimages of Permutation Classes, arXiv:1809.03123 [math.CO], 2018.
Katie R. Gedeon, Kazhdan-Lusztig polynomials of thagomizer matroids, arXiv:1610.05349 [math.CO], 2016.
Y. Park, S. Park, Avoiding permutations and the Narayana numbers, J. Korean Math. Soc. 50 (2013), No. 3, pp. 529-541.
Lara Pudwell, On the distribution of peaks (and other statistics), 16th International Conference on Permutation Patterns, Dartmouth College, 2018.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
Chao-Jen Wang, Applications of the Goulden-Jackson cluster method to counting Dyck paths by occurrences of subwords.
Philip B. Zhang and Sergey Kitaev, Descent generating polynomials for (n-3)- and (n-4)-stack-sortable (pattern-avoiding) permutations, Discrete Applied Mathematics, Volume 372, 2025, Pages 1-14.
Index entries for sequences related to Łukasiewicz

Cf. A000108, A001791, A243752.

T(n,k) are rational multiples of A055151.

a := (n,k)->binomial(n+1,k)* add(binomial(k+j-1,k-1)*binomial(n+1-k, n-2*k-j), j=0..n-2*k)/(n+1); seq(seq(a(n,k), k=0..floor(n/2)),n=0..15);
seq(seq(simplify(n!*(1+k)/((n-2*k)!*(1+k)!^2)*hypergeom([k,2*k-n],[k+2],-1)),k=0.. floor(n/2)),n=0..15); # Peter Luschny, Oct 16 2015
# alternative Maple program:
b:= proc(x, y) option remember; `if`(y>x or y<0, 0,
      `if`(x=0, 1, expand(b(x-1, y)*`if`(y=0, 1, 2)*z+
       b(x-1, y+1) +b(x-1, y-1))))
    end:
T:= n-> (p-> seq(coeff(p, z, n-2*i), i=0..n/2))(b(n, 0)):
seq(T(n), n=0..15);  # Alois P. Heinz, Aug 07 2018

T[n_, k_] := Binomial[n+1, k]*Sum[Binomial[k+j-1, k-1]*Binomial[n+1-k, n- 2*k-j], {j, 0, n-2*k}]/(n+1); Table[T[n, k], {n, 0, 15}, {k, 0, Floor[n/2 ]}] // Flatten (* Jean-François Alcover, Jan 31 2016 *)

tabf(nn) = {for(n=-1, nn, for(k=0, floor(n/2), if(binomial(n+1,k) * sum(j=0, n-2*k, binomial(k+j-1,k-1) * binomial(n+1-k,n-2*k-j))/(n+1)==0,print1("1, "), print1(binomial(n+1,k) * sum(j=0, n-2*k, binomial(k+j-1,k-1) * binomial(n+1-k,n-2*k-j))/(n+1),", "));); print();); };
tabf(16); \\ Indranil Ghosh, Mar 05 2017

T(n,k) = (1/(n+1)) * binomial(n+1, k) * Sum_{j=0..n-2k} binomial(k+j-1, k-1)*binomial(n+1-k, n-2k-j).
G.f. G(t, z) satisfies z*(1-z+t*z)*G^2 - G + 1 = 0.
T(n,k) = n!*(1+k)/((n-2*k)!*(1+k)!^2)*hypergeom([k,2*k-n], [k+2], -1). - Peter Luschny, Oct 16 2015
T(n,k) = A055151(n,k)*hypergeom([k,2*k-n],[k+2],-1). - Peter Luschny, Oct 16 2015

Edited by Andrew Baxter, May 17 2011

A114463 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k ascents of length 2 starting at an odd level (0<=k<=floor(n/2)-1 for n>=2; k=0 for n=0,1).

Original entry on oeis.org

1, 1, 2, 5, 13, 1, 36, 6, 105, 26, 1, 317, 104, 8, 982, 402, 45, 1, 3105, 1522, 225, 10, 9981, 5693, 1052, 69, 1, 32520, 21144, 4698, 412, 12, 107157, 78188, 20319, 2249, 98, 1, 356481, 288340, 85864, 11522, 679, 14, 1195662, 1061520, 356535, 56360, 4230

Offset: 0

Emeric Deutsch, Nov 29 2005

Row n (n>=2) has floor(n/2) terms. Row sums are the Catalan numbers (A000108). Sum(kT(n,k),k=0..floor(n/2)-1)=binomial(2n-4,n) (A002694). Column 0 yields A114465.

			T(5,1) = 6 because we have UUD(UU)DUDDD, UUD(UU)DDUDD, UUD(UU)DDDUD,
UDUUD(UU)DDD, UUDUD(UU)DDD and UUUDD(UU)DDD, where U=(1,1), D=(1,-1) (the ascents of length 2 starting at an odd level are shown between parentheses; note that the fourth path has an ascent of length 2 that starts at an even level).
Triangle starts:
:  0 :    1;
:  1 :    1;
:  2 :    2;
:  3 :    5;
:  4 :   13,    1;
:  5 :   36,    6;
:  6 :  105,   26,    1;
:  7 :  317,  104,    8;
:  8 :  982,  402,   45,  1;
:  9 : 3105, 1522,  225, 10;
: 10 : 9981, 5693, 1052, 69, 1;

Alois P. Heinz, Rows n = 0..200, flattened

Cf. A114462, A114464, A114465, A000108, A002694, A243752.

G:=-1/2*(1-z^2+z^2*t-sqrt((z^2*t-z^2+4*z-1)*(z^2*t-z^2-1)))/z/(-z^2+z^2*t+z-z*t-1): Gser:=simplify(series(G,z=0,18)): P[0]:=1: for n from 1 to 15 do P[n]:=coeff(Gser,z^n) od: 1; 1; for n from 2 to 15 do seq(coeff(t*P[n],t^j),j=1..floor(n/2)) od; # 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, 2, 5, 2][t])
      *`if`(t=5, z, 1) +b(x-1, y-1, [1, 3, 4, 1, 3][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

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, 2, 5, 2}[[t]]]*If[t==5, z, 1] + b[x-1, y-1, {1, 3, 4, 1, 3}[[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, Mar 31 2015, after Alois P. Heinz *)

G.f.: G=G(t, z) satisfies z[(1-t)z^2-(1-t)z+1]G^2-[1-(1-t)z^2]G+1=0.

cp's OEIS Frontend

A243833 Number A(n,k) of Dyck paths of semilength n having exactly seven (possibly overlapping) occurrences 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

A243834 Number A(n,k) of Dyck paths of semilength n having exactly eight (possibly overlapping) occurrences 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

A243835 Number A(n,k) of Dyck paths of semilength n having exactly nine (possibly overlapping) occurrences 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

A243836 Number A(n,k) of Dyck paths of semilength n having exactly ten (possibly overlapping) occurrences 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

A243881 Number T(n,k) of Dyck paths of semilength n having exactly k (possibly overlapping) occurrences of the consecutive steps UDUUUDDDUD (with U=(1,1), D=(1,-1)); triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/4)), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A091869 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k peaks at even height.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A131427 A000108(n) preceded by n zeros.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

A091156 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having k long ascents (i.e., ascents of length at least 2). Rows are of length 1,1,2,2,3,3,... .

Views