A371928
T(n,k) is the total number of levels in all Dyck paths of semilength 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, 1, 1, 1, 3, 1, 3, 5, 6, 1, 8, 15, 13, 11, 1, 23, 44, 43, 29, 20, 1, 71, 134, 138, 106, 62, 37, 1, 229, 427, 446, 371, 248, 132, 70, 1, 759, 1408, 1478, 1275, 941, 571, 283, 135, 1, 2566, 4753, 5017, 4410, 3437, 2331, 1310, 611, 264, 1, 8817, 16321, 17339, 15458, 12426, 9027, 5709, 3002, 1324, 521, 1
Offset: 0
In the A000108(3) = 5 Dyck paths of semilength 3 there are 3 levels with 1 node, 5 levels with 2 nodes, 6 levels with 3 nodes, and 1 level with 4 nodes.
1
2 /\ 2 1 1
2 / \ 3 /\/\ 3 /\ 3 /\ 3
2 / \ 2 / \ 3 / \/\ 3 /\/ \ 4 /\/\/\ .
So row 3 is [3, 5, 6, 1].
Triangle T(n,k) begins:
1;
1, 1;
1, 3, 1;
3, 5, 6, 1;
8, 15, 13, 11, 1;
23, 44, 43, 29, 20, 1;
71, 134, 138, 106, 62, 37, 1;
229, 427, 446, 371, 248, 132, 70, 1;
759, 1408, 1478, 1275, 941, 571, 283, 135, 1;
2566, 4753, 5017, 4410, 3437, 2331, 1310, 611, 264, 1;
8817, 16321, 17339, 15458, 12426, 9027, 5709, 3002, 1324, 521, 1;
...
-
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>0, g(x-1, y-1, p), 0)
end:
T:= n-> (p-> seq(coeff(p, z, i), i=1..n+1))(g(2*n, 0$2)):
seq(T(n), n=0..10);
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
- 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.
-
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
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
-
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);
Showing 1-3 of 3 results.
Comments