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
Examples
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.
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.
Programs
-
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
-
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 *) -
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
-
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
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
Extensions
Edited by Robert G. Wilson v, Jun 25 2002
Comments