A333498 -id:A333498 - cp's OEIS frontend

A333504 Sum of the heights of all lattice paths from (0,0) to (n,0) that do not go below the x-axis, and at (x,y) only allow steps (1,v) with v in {-1,0,1,...,y+1}.

0, 0, 1, 3, 9, 28, 88, 282, 921, 3058, 10302, 35159, 121406, 423704, 1493046, 5307276, 19014642, 68609686, 249149529, 910000728, 3341113126, 12325295866, 45664033813, 169846998495, 634020229888, 2374550269819, 8920273989351, 33604033638696, 126919824985533

Offset: 0

Alois P. Heinz, Mar 24 2020

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..400
Wikipedia, Counting lattice paths

Cf. A333069, A333070, A333071, A333498, A333608.

b:= proc(x, y, h) option remember; `if`(x=0, h, add((t->
     `if`(x>t, b(x-1, t, max(h, t)), 0))(y-j), j=-1-y..min(1, y)))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..33);

b[x_, y_, h_] := b[x, y, h] = If[x == 0, h, Sum[With[{t = y - j},
     If[x > t, b[x - 1, t, Max[h, t]], 0]], {j, -1 - y, Min[1, y]}]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 33] (* Jean-François Alcover, Apr 26 2021, after Alois P. Heinz *)

A333608 Sum of the heights of all nonnegative lattice paths from (0,0) to (n,0) where the allowed steps at (x,y) are (1,v) with v in {-1,0,...,max(y,1)}.

Original entry on oeis.org

0, 0, 1, 3, 9, 25, 70, 200, 584, 1742, 5304, 16471, 52120, 167885, 549856, 1828897, 6170108, 21087458, 72923515, 254880303, 899454849, 3201729220, 11486266036, 41497996004, 150879471934, 551723923040, 2027990653855, 7489507917594, 27777837416779, 103427750936183

Offset: 0

Alois P. Heinz, Mar 28 2020

nonn

The maximal height in all paths of length n is A103354(n-1).

Alois P. Heinz, Table of n, a(n) for n = 0..500
Wikipedia, Counting lattice paths
Wikipedia, Motzkin number

Cf. A103354, A333105, A333106, A333107, A333498, A333504.

b:= proc(x, y, h) option remember;
     `if`(x=0, h, add(b(x-1, y+j, max(y, h)),
      j=-min(1, y)..min(max(1, y), x-y-1)))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..29);

b[x_, y_, h_] := b[x, y, h] = If[x == 0, h, Sum[b[x - 1, y + j, Max[y, h]], {j, -Min[1, y], Min[Max[1, y], x - y - 1]}]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 29] (* Jean-François Alcover, May 12 2020, after Maple *)

A057585 Area under Motzkin excursions.

Original entry on oeis.org

0, 1, 4, 16, 56, 190, 624, 2014, 6412, 20219, 63284, 196938, 610052, 1882717, 5792528, 17776102, 54433100, 166374109, 507710420, 1547195902, 4709218604, 14318240578, 43493134160, 132003957436, 400337992056, 1213314272395, 3674980475284, 11124919273160

Offset: 1

Cyril Banderier, Oct 04 2000

a(n) is the sum of areas under all Motzkin excursions of length n (nonnegative walks beginning and ending in 0, with jumps -1,0,+1).

T. D. Noe, Table of n, a(n) for n = 1..400
C. Banderier, Analytic combinatorics of random walks and planar maps, PhD Thesis, 2001.
AJ Bu, Explicit Generating Functions for the Sum of the Areas Under Dyck and Motzkin Paths (and for Their Powers), arXiv:2310.17026 [math.CO], 2023.
AJ Bu and Doron Zeilberger, Using Symbolic Computation to Explore Generalized Dyck Paths and Their Areas, arXiv:2305.09030 [math.CO], 2023.

Cf. A001006, A333498.

G:= (x^2+2*x-1+(-x+1)*sqrt((x+1)*(1-3*x)))/(2*(3*x-1)*(x+1)*x^2): Gser:=series(G,x=0,30): seq(coeff(Gser,x,n),n=1..26); # Emeric Deutsch, Apr 08 2007

f[x_] := (x^2+2*x-1+(-x+1)*Sqrt[(x+1)*(1-3*x)]) / (2*(3*x-1)*(x+1)*x^2); Drop[ CoefficientList[ Series[ f[x], {x, 0, 26}], x], 1] (* Jean-François Alcover, Dec 21 2011, from g.f. *)

G.f.: (x^2 + 2*x - 1 + (-x+1)*sqrt((x+1)*(1-3*x)))/(2*(3*x-1)*(x+1)*x^2).
Recurrence: (n-2)*(n+2)*a(n) = (n+1)*(4*n-7)*a(n-1) + (2*n^2 - 3*n - 8)*a(n-2) - 3*(n-1)*(4*n-5)*a(n-3) - 9*(n-2)*(n-1)*a(n-4). - Vaclav Kotesovec, Sep 11 2013
a(n) ~ 3^(n+1)/4 * (1-2*sqrt(3)/sqrt(Pi*n)). - Vaclav Kotesovec, Sep 11 2013

A097862 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n and height k (n>=0, k>=0).

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 7, 1, 1, 15, 5, 1, 31, 18, 1, 1, 63, 56, 7, 1, 127, 161, 33, 1, 1, 255, 441, 129, 9, 1, 511, 1170, 453, 52, 1, 1, 1023, 3036, 1485, 242, 11, 1, 2047, 7753, 4644, 990, 75, 1, 1, 4095, 19565, 14040, 3718, 403, 13, 1, 8191, 48930, 41392, 13145, 1872, 102

Offset: 0

Emeric Deutsch, Sep 01 2004

Row sums are the Motzkin numbers (A001006).

			Triangle begins:
  1;
  1;
  1,   1;
  1,   3;
  1,   7,    1;
  1,  15,    5;
  1,  31,   18,   1;
  1,  63,   56,   7;
  1, 127,  161,  33,  1;
  1, 255,  441, 129,  9;
  1, 511, 1170, 453, 52, 1;
  ...
Row n contains 1+floor(n/2) terms.
T(5,2) = 5 counts HUUDD, UUDDH, UUDHD, UHUDD and UUHDD, where U=(1,1), H=(1,0) and D=(1,-1).

Alois P. Heinz, Rows n = 0..200, flattened
Richard J. Mathar, Motzkin Islands: a 3-dimensional Embedding of Motzkin Paths, viXra:2009.0152, 2020.

Cf. A001006, A333498.

P[0]:=1: P[1]:=1-z: for n from 2 to 10 do P[n]:=sort(expand((1-z)*P[n-1]-z^2*P[n-2])) od: for k from 0 to 8 do h[k]:=series(z^(2*k)/P[k]/P[k+1],z=0,20) od: a:=proc(n,k) if k=0 then 1 elif n=0 then 0 else coeff(h[k],z^n) fi end: seq(seq(a(n,k),k=0..floor(n/2)),n=0..15);
# second Maple program:
b:= proc(x, y, h) option remember; `if`(x=0, z^h, add(
      b(x-1, y+j, max(h, y)), j=-min(1, y)..min(1, x-y-1)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..16);  # Alois P. Heinz, Mar 13 2017, revised Mar 28 2020

b[x_, y_, m_] := b[x, y, m] = If[y > x, 0, If[x == 0, z^m, If[y > 0, b[x - 1, y - 1, m], 0] + b[x - 1, y, m] + b[x - 1, y + 1, Max[m, y + 1]]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][ b[n, 0, 0]];
Table[T[n], {n, 0, 16}] // Flatten (* Jean-François Alcover, May 12 2017, after Alois P. Heinz *)

The g.f. for column k is z^(2k)/[P_k*P_{k+1}], where the polynomials P_k are defined by P_0=1, P_1=1-z, P_k=(1-z)P_{k-1}-z^2*P_{k-2}.

Sum_{k=1..floor(n/2)} k * T(n,k) = A333498(n). - Alois P. Heinz, Mar 28 2020

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

A136439 Sum of heights of all 1-watermelons with wall of length 2*n.

Original entry on oeis.org

1, 3, 10, 34, 118, 417, 1495, 5421, 19838, 73149, 271453, 1012872, 3797228, 14294518, 54006728, 204702328, 778115558, 2965409556, 11327549778, 43361526366, 166306579062, 638969153207, 2458973656584, 9477124288144, 36576265716636, 141344492073392, 546860238004919

Offset: 1

Steven Finch, Apr 02 2008

nonn

a(n) is the sum of heights of all Dyck excursions of length 2*n (nonnegative walks beginning and ending at 0 with jumps -1,+1).

N. G. de Bruijn, D. E. Knuth and S. O. Rice, The average height of planted plane trees, in: Graph Theory and Computing (ed. T. C. Read), Academic Press, New York, 1972, pp. 15-22.

François Marques, Table of n, a(n) for n = 1..1500 (first 650 terms from Alois P. Heinz)
N. Dershowitz and C. Rinderknecht, The Average Height of Catalan Trees by Counting Lattice Paths, Preprint, 2015. Contains more information about the asymptotic behavior than was included in the published version. [Included with permission]
N. Dershowitz and C. Rinderknecht, The Average Height of Catalan Trees by Counting Lattice Paths, Math. Mag., 88 (No. 3, 2015), 187-195.
M. Fulmek, Asymptotics of the average height of 2-watermelons with a wall, Elec. J. Combin. 14 (2007) R64.
S. Gilliand, C. Johnson, S. Rush, D. Wood, The sock matching problem, Involve, a Journal of Mathematics, Vol. 7 (2014), No. 5, 691-697; DOI: 10.2140/involve.2014.7.691.

Cf. A000108, A008549, A078920, A261003, A333498.

H[0]:=1: for k to 30 do H[k]:=simplify(1/(1-z*H[k-1])) end do: g:=sum(j*(H[j]-H[j-1]),j=1..30): gser:=series(g,z=0,27): seq(coeff(gser,z,n),n=1..24); # Emeric Deutsch, Apr 13 2008
# second Maple program:
b:= proc(x, y, h) option remember; `if`(x=0, h, add(`if`(x+j>y,
      b(x-1, y-j, max(h, y-j)), 0), j={$-1..min(1, y)} minus {0}))
    end:
a:= n-> b(2*n, 0$2):
seq(a(n), n=1..33);  # Alois P. Heinz, Mar 24 2020

c[n_] := (2*n)!/(n!*(n+1)!)
s[n_,a_] := Sum[If[k < 1, 0, DivisorSigma[0,k]*Binomial[2*n,n+a-k]/Binomial[2*n,n]], {k,a-n,a+n}]
h[n_] := (n+1)*(s[n,1]-2*s[n,0]+s[n,-1]) - 1
a[n_] := h[n]*c[n]

\\ Translation of Mathematica code
s(n,a)=sum(k=1,a+n, numdiv(k)*binomial(2*n,n+a-k))/binomial(2*n,n)
a(n)=((n+1)*(s(n,1)-2*s(n,0)+s(n,-1))-1)*binomial(2*n,n)/(n+1) \\ Charles R Greathouse IV, Mar 28 2016

G.f.: Sum_{k >= 1} k*(H[k]-H[k-1]), where H[0]=1 and H[k]=1/(1-zH[k-1]) for k=1,2,... (the first Maple program makes use of this g.f.). - Emeric Deutsch, Apr 13 2008

More terms from Alois P. Heinz, Mar 24 2020

A372033 The total number of levels visited by all Motzkin paths of length n.

Original entry on oeis.org

1, 1, 3, 7, 18, 46, 121, 323, 875, 2395, 6611, 18371, 51337, 144145, 406420, 1150126, 3265412, 9298372, 26547710, 75978322, 217921336, 626287520, 1803176384, 5200298000, 15020569818, 43447201226, 125837214564, 364911724264, 1059404265599, 3078918594707

Offset: 0

Alois P. Heinz, Apr 16 2024

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, Motzkin number

Row sums of A372014.

Cf. A001006, A261003, A333498.

b:= proc(x, y, h) option remember; `if`(x=0, h+1, add(
      b(x-1, y+j, max(h, y)), j=-min(1, y)..min(1, x-y-1)))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..35);

a(n) = A001006(n) + A333498(n).

cp's OEIS Frontend

A333504 Sum of the heights of all lattice paths from (0,0) to (n,0) that do not go below the x-axis, and at (x,y) only allow steps (1,v) with v in {-1,0,1,...,y+1}.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A333608 Sum of the heights of all nonnegative lattice paths from (0,0) to (n,0) where the allowed steps at (x,y) are (1,v) with v in {-1,0,...,max(y,1)}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A057585 Area under Motzkin excursions.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A097862 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n and height k (n>=0, k>=0).

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

A136439 Sum of heights of all 1-watermelons with wall of length 2*n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A372033 The total number of levels visited by all Motzkin paths of length n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula