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
Keywords
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.
Programs
-
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] -
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
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
Extensions
More terms from Alois P. Heinz, Mar 24 2020
Comments