A088457 -id:A088457 - cp's OEIS frontend

A152880 Number of Dyck paths of semilength n having exactly one peak of maximum height.

1, 1, 3, 8, 23, 71, 229, 759, 2566, 8817, 30717, 108278, 385509, 1384262, 5006925, 18225400, 66711769, 245400354, 906711758, 3363516354, 12522302087, 46773419089, 175232388955, 658295899526, 2479268126762, 9359152696924, 35406650450001, 134215036793130

Offset: 1

Emeric Deutsch, Jan 02 2009

nonn

Also number of peaks of maximum height in all Dyck paths of semilength n-1. Example: a(3)=3 because in (UD)(UD) and U(UD)D we have three peaks of maximum height (shown between parentheses).

			a(3)=3 because we have UU(UD)DD, UDU(UD)D, U(UD)DUD, where U=(1,1), D=(1,-1), with the peak of maximum height shown between parentheses; the path UUDUDD does not qualify because it has two peaks of maximum height.

Alois P. Heinz, Table of n, a(n) for n = 1..500
Miklos Bona and Elijah DeJonge, Pattern avoiding permutations and involutions with a unique longest increasing subsequence, arXiv:2003.10640 [math.CO], 2020.
Miklós Bóna and Elijah DeJonge, Pattern Avoiding Permutations and Involutions with a Unique Longest Increasing Subsequence, (2020).

Cf. A088457, A152879.

Column k=1 of A371928.

f[0] := 1: f[1] := 1: for i from 2 to 35 do f[i] := sort(expand(f[i-1]-z*f[i-2])) end do; g := sum(z^j/f[j]^2, j = 1 .. 34): gser := series(g, z = 0, 30): seq(coeff(gser, z, n), n = 1 .. 27);
# second Maple program:
b:= proc(x, y, h, c) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, c, add(b(x-1, y-i, max(h, y), `if`(h=y, 0,
     `if`(h b(2*n, 0$3):
seq(a(n), n=1..28);  # Alois P. Heinz, Jul 25 2023

b[x_, y_, h_, c_] := b[x, y, h, c] = If[y<0 || y>x, 0, If[x==0, c, Sum[b[x-1, y-i, Max[h, y], If[h==y, 0, If[hJean-François Alcover, Sep 17 2024, after Alois P. Heinz *)

G.f.: g(z) = Sum_{j>=1} z^j/f(j)^2, where the f(j)'s are the Fibonacci polynomials (in z) defined by f(0)=f(1)=1, f(j)=f(j-1)-zf(j-2), j>=2.
a(n) = A152879(n,1).
a(n) = Sum_{k=1..n} k*A152879(n-1,k).

A372014 T(n,k) is the total number of levels in all Motzkin paths of length n containing exactly k path nodes; triangle T(n,k), n>=0, 1<=k<=n+1, read by rows.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 2, 2, 2, 1, 4, 6, 4, 3, 1, 8, 14, 12, 7, 4, 1, 18, 32, 33, 21, 11, 5, 1, 44, 74, 84, 64, 34, 16, 6, 1, 113, 180, 208, 181, 111, 52, 22, 7, 1, 296, 457, 520, 485, 344, 179, 76, 29, 8, 1, 782, 1195, 1334, 1273, 1000, 599, 274, 107, 37, 9, 1

Offset: 0

Alois P. Heinz, Apr 15 2024

A Motzkin path of length n has n+1 nodes.

			In the A001006(3) = 4 Motzkin paths of length 3 there are 2 levels with 1 node, 2 levels with 2 nodes, 2 levels with 3 nodes, and 1 level with 4 nodes.
  2  _     1        1
  2 / \    3 /\_    3 _/\    4 ___    .
  So row 3 is [2, 2, 2, 1].
Triangle T(n,k) begins:
    1;
    0,    1;
    1,    1,    1;
    2,    2,    2,    1;
    4,    6,    4,    3,    1;
    8,   14,   12,    7,    4,   1;
   18,   32,   33,   21,   11,   5,   1;
   44,   74,   84,   64,   34,  16,   6,   1;
  113,  180,  208,  181,  111,  52,  22,   7,  1;
  296,  457,  520,  485,  344, 179,  76,  29,  8, 1;
  782, 1195, 1334, 1273, 1000, 599, 274, 107, 37, 9, 1;
  ...

Alois P. Heinz, Rows n = 0..28, flattened
Wikipedia, Motzkin number

Columns k=1-2 give: A088457, A051485.
Row sums give A372033 = A001006 + A333498.
Cf. A005717, A371928.

g:= proc(x, y, p) (h-> `if`(x=0, add(z^coeff(h, z, i)
          , i=0..degree(h)), b(x, y, h)))(p+z^y) end:
b:= proc(x, y, p) option remember; `if`(y+2<=x, g(x-1, y+1, p), 0)
      +`if`(y+1<=x, g(x-1, y, p), 0)+`if`(y>0, g(x-1, y-1, p), 0)
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=1..n+1))(g(n, 0$2)):
seq(T(n), n=0..10);

Sum_{k=1..n+1} k * T(n,k) = A005717(n+1) = (n+1) * A001006(n).

A051485 Number of double nodes (exactly two nodes on that level) for all Motzkin paths of length n.

Original entry on oeis.org

0, 1, 1, 2, 6, 14, 32, 74, 180, 457, 1195, 3177, 8526, 23018, 62441, 170153, 465791, 1280956, 3538618, 9817619, 27348480, 76467497, 214532805, 603732396, 1703728554, 4819990947, 13667248631, 38834528740, 110556072877, 315290709729, 900635841754, 2576615923655, 7381956798465, 21177682172332, 60832837964492

Offset: 0

Wenjin Woan

nonn

			Of the 9 Motzkin paths of length 4 the following 5 have a total of 6 double nodes:
|1......|
|2../\..|3..__..|2.._...|2..._..|2......|
|2./..\.|2./..\.|3./.\_.|3._/.\.|3./\/\.|

Cf. A001006, A088457.

Column k=2 of A372014.

Edited by Michael Somos, Sep 29 2003

a(16)-a(34) from Alois P. Heinz, Apr 13 2024

A364386 Triangle T(n,k) read by rows: the number of Motzkin paths of length n that have k nodes at their peak level, 1 <= k <= n+1.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 8, 7, 4, 1, 0, 1, 18, 15, 11, 5, 1, 0, 1, 44, 33, 26, 16, 6, 1, 0, 1, 113, 78, 59, 42, 22, 7, 1, 0, 1, 296, 197, 138, 101, 64, 29, 8, 1, 0, 1, 782, 518, 342, 240, 165, 93, 37, 9, 1, 0, 1, 2076, 1388, 892, 590, 406, 258, 130, 46, 10, 1, 0, 1

Offset: 0

R. J. Mathar, Jul 21 2023

			Example for 9 paths of length n=4: UUDD (k=1 at level 2), UHHD (k=3 at level 1), UHDH (k=2 at level 1), UDUD (k=2 at level 1), UDHH (k=1 at level 1), HUHD (k=2 at level 1), HUDH (k=1 at level 1), HHUD (k=1 at level 1), HHHH (k=5 at level 0). So k=1 appears 4 times, k=2 3 times, k=3 once, k=4 never, k=5 once.
The triangle starts:
      1
      0,     1
      1,     0,    1
      2,     1,    0,    1
      4,     3,    1,    0,    1
      8,     7,    4,    1,    0,    1
     18,    15,   11,    5,    1,    0,    1
     44,    33,   26,   16,    6,    1,    0,   1
    113,    78,   59,   42,   22,    7,    1,   0,   1
    296,   197,  138,  101,   64,   29,    8,   1,   0,  1
    782,   518,  342,  240,  165,   93,   37,   9,   1,  0,  1
   2076,  1388,  892,  590,  406,  258,  130,  46,  10,  1,  0, 1
   5538,  3747, 2401, 1522, 1005,  665,  388, 176,  56, 11,  1, 0, 1
  14856, 10147, 6560, 4085, 2576, 1680, 1054, 564, 232, 67, 12, 1, 0, 1
  ...

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

Cf. A001006 (row sums), A088457 (column k=1).

Cf. A152879 (equivalent for Dyck paths).

T(n,n) = 1. (All nodes on level 0, only H steps.)
T(n,n-1) = 0.
T(n,n-2) = 1. (steps UHHH...HHHD)

cp's OEIS Frontend

A152880 Number of Dyck paths of semilength n having exactly one peak of maximum height.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A372014 T(n,k) is the total number of levels in all Motzkin paths of length n containing exactly k path nodes; triangle T(n,k), n>=0, 1<=k<=n+1, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A051485 Number of double nodes (exactly two nodes on that level) for all Motzkin paths of length n.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A364386 Triangle T(n,k) read by rows: the number of Motzkin paths of length n that have k nodes at their peak level, 1 <= k <= n+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula