login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A071688 Number of plane trees with even number of leaves. 4
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 (list; graph; refs; listen; history; text; internal format)
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,2k)*C(n,2k+j) - C(n,2k-1) * C(n,2k+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: A320740 A320741 A292503 * A232687 A211602 A110149

Adjacent sequences:  A071685 A071686 A071687 * A071689 A071690 A071691

KEYWORD

easy,nonn

AUTHOR

Sen-peng Eu, Jun 23 2002

EXTENSIONS

Edited by Robert G. Wilson v, Jun 25 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 4 08:33 EDT 2020. Contains 335444 sequences. (Running on oeis4.)