OFFSET
1,2
COMMENTS
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).
REFERENCES
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.
LINKS
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.
FORMULA
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
MAPLE
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
MATHEMATICA
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]
PROG
(PARI) \\ 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
CROSSREFS
KEYWORD
nonn
AUTHOR
Steven Finch, Apr 02 2008
EXTENSIONS
More terms from Alois P. Heinz, Mar 24 2020
STATUS
approved