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

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,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

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

Sequence in context: A071725 A026016 A109263 * A371819 A178578 A188622

Adjacent sequences: A136436 A136437 A136438 * A136440 A136441 A136442

Keyword

nonn

Author

Steven Finch, Apr 02 2008

Extensions

More terms from Alois P. Heinz, Mar 24 2020

Status

approved