%I #42 Oct 15 2020 05:25:23

%S 1,3,10,34,118,417,1495,5421,19838,73149,271453,1012872,3797228,

%T 14294518,54006728,204702328,778115558,2965409556,11327549778,

%U 43361526366,166306579062,638969153207,2458973656584,9477124288144,36576265716636,141344492073392,546860238004919

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

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

%D 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.

%H François Marques, <a href="/A136439/b136439.txt">Table of n, a(n) for n = 1..1500</a> (first 650 terms from Alois P. Heinz)

%H N. Dershowitz and C. Rinderknecht, <a href="/A136439/a136439.pdf">The Average Height of Catalan Trees by Counting Lattice Paths</a>, Preprint, 2015. Contains more information about the asymptotic behavior than was included in the published version. [Included with permission]

%H N. Dershowitz and C. Rinderknecht, <a href="http://www.jstor.org/stable/10.4169/math.mag.88.3.187">The Average Height of Catalan Trees by Counting Lattice Paths</a>, Math. Mag., 88 (No. 3, 2015), 187-195.

%H M. Fulmek, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v14i1r64">Asymptotics of the average height of 2-watermelons with a wall</a>, Elec. J. Combin. 14 (2007) R64.

%H S. Gilliand, C. Johnson, S. Rush, D. Wood, <a href="http://dx.doi.org/10.2140/involve.2014.7.691">The sock matching problem</a>, Involve, a Journal of Mathematics, Vol. 7 (2014), No. 5, 691-697; DOI: 10.2140/involve.2014.7.691.

%F 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

%p 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

%p # second Maple program:

%p b:= proc(x, y, h) option remember; `if`(x=0, h, add(`if`(x+j>y,

%p b(x-1, y-j, max(h, y-j)), 0), j={$-1..min(1, y)} minus {0}))

%p end:

%p a:= n-> b(2*n, 0$2):

%p seq(a(n), n=1..33); # _Alois P. Heinz_, Mar 24 2020

%t c[n_] := (2*n)!/(n!*(n+1)!)

%t 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}]

%t h[n_] := (n+1)*(s[n,1]-2*s[n,0]+s[n,-1]) - 1

%t a[n_] := h[n]*c[n]

%o (PARI) \\ Translation of Mathematica code

%o s(n,a)=sum(k=1,a+n, numdiv(k)*binomial(2*n,n+a-k))/binomial(2*n,n)

%o 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

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

%K nonn

%O 1,2

%A _Steven Finch_, Apr 02 2008

%E More terms from _Alois P. Heinz_, Mar 24 2020