A071688 Number of plane trees with even number of leaves.

0, 1, 3, 7, 20, 66, 217, 715, 2424, 8398, 29414, 104006, 371384, 1337220, 4847637, 17678835, 64821680, 238819350, 883634026, 3282060210, 12233125112, 45741281820, 171529836218, 644952073662, 2430973096720, 9183676536076, 34766775829452, 131873975875180, 501121106988464

Offset

1,3

Comments

Number of Dyck n-paths with an even number of peaks (or, equivalently, odd number of valleys). - Yu Hin Au, Dec 07 2019

Links

G. C. Greubel, Table of n, a(n) for n = 1..1000

Yu Hin (Gary) Au, Some Properties and Combinatorial Implications of Weighted Small Schröder Numbers, arXiv:1912.00555 [math.CO], 2019.

S. P. Eu, S. C. Liu and Y. N. Yeh, Odd or Even on Plane Trees, Discrete Mathematics, Volume 281, Issues 1-3, 28 April 2004, Pages 189-196.

Formula

a(2n) = (1/(4*n+2))*binomial(4*n, 2*n), a(2n+1) = (1/(4*n+4))*binomial(4*n+2, 2*n+1) + (-1)^(n+1)*(1/(2*n+2))*binomial(2*n, n).

G.f.: (1/4)*(2-(1-4*x)^(1/2) + 2*x - (1+4*x^2)^(1/2))/x. - Vladeta Jovovic, Apr 19 2003

a(0)=1, a(n) = Sum_{k=0..floor(n/2)} (1/n)*C(n,2k-1)*C(n,2k), n>0. - Paul Barry, Jan 25 2007

a(n) = 0^n + Sum_{k=1..n} (1/n)*C(n,k)*C(n,k-1)*(1+(-1)^k)/2. - Paul Barry, Dec 16 2008

a(n) = Sum_{k=0..n} Sum_{j=0..n-k} (-1)^j*(C(n,2*k)*C(n,2*k+j) - C(n,2*k-1)*C(n,2*k+j+1)). - Paul Barry, Sep 13 2010

n*(n+1)*a(n) -2*n*(n+1)*a(n-1) - 4*(2*n^2 -10*n +9)*a(n-2) +8*(n^2 -11*n + 21)*a(n-3) -48*(n-3)*(n-4)*a(n-4) + 32*(2*n-9)*(n-5)*a(n-5) = 0. - R. J. Mathar, Nov 24 2012 (corrected by Yu Hin Au, Dec 09 2019 )

a(n) = (A000108(n) - 2^n * binomial(1/2, (n+1)/2))/2. - Vladimir Reshetnikov, Oct 03 2016

From Vaclav Kotesovec, Oct 04 2016: (Start)

Recurrence (of order 3): n*(n+1)*(5*n^2 - 20*n + 18)*a(n) = 2*n*(2*n - 5)*(5*n^2 - 10*n + 3)*a(n-1) - 4*(n-2)*n*(5*n^2 - 20*n + 18)*a(n-2) + 8*(n-3)*(2*n - 5)*(5*n^2 - 10*n + 3)*a(n-3).

a(n) ~ 2^(2*n-1)/(sqrt(Pi*n)*n).

(End)

a(n) = A119358(n) - A119359(n) = hypergeom([1/2-n/2, 1/2-n/2, -n/2, -n/2], [1/2, 1/2, 1], 1) - hypergeom([-1/2-n/2, 1/2-n/2, 1-n/2, -n/2], [1/2, 1/2, 1], 1). - Vladimir Reshetnikov, Oct 05 2016

Example

a(3) = 3 because among the 5 plane 3-trees there are 3 trees with even number of leaves; a(4) = 7 because among the 14 plane 4-trees there are 7 trees with even number of leaves.

Maple

seq( add(2*k*binomial(n, 2*k)^2/(n*(n-2*k+1)), k=0..floor(n/2)), n=1..30); # G. C. Greubel, Dec 10 2019

Mathematica

a[n_] := If[EvenQ[n], Binomial[2n, n]/(2n + 2), Binomial[2n, n]/(2n + 2) + (-1)^((n + 1)/2)Binomial[n - 1, (n - 1)/2]/(n + 1)]
Table[(CatalanNumber[n] - 2^n Binomial[1/2, (n + 1)/2])/2, {n, 20}] (* Vladimir Reshetnikov, Oct 03 2016 *)

Prog

(PARI) a(n) = 0^n + sum(k=1, n, (1/n)*binomial(n, k)*binomial(n, k-1)*(1+(-1)^k)/2); \\ Michel Marcus, Dec 09 2019
(Magma) [ &+[2*k*Binomial(n, 2*k)^2/(n*(n-2*k+1)): k in [0..Floor(n/2)]] : n in [1..30]]; // G. C. Greubel, Dec 10 2019
(Sage) [ sum(2*k*binomial(n, 2*k)^2/(n*(n-2*k+1)) for k in (0..floor(n/2))) for n in (1..30)] # G. C. Greubel, Dec 10 2019

Crossrefs

a(n) + A071684 = A000108: Catalan numbers.

Cf. A007595.

Sequence in context: A320741 A292503 A340357 * A232687 A211602 A110149

Adjacent sequences: A071685 A071686 A071687 * A071689 A071690 A071691

Keyword

easy,nonn,changed

Author

Sen-peng Eu, Jun 23 2002

Extensions

Edited by Robert G. Wilson v, Jun 25 2002

Status

approved