|
%I #52 Jan 01 2023 06:07:30
%S 0,1,3,7,20,66,217,715,2424,8398,29414,104006,371384,1337220,4847637,
%T 17678835,64821680,238819350,883634026,3282060210,12233125112,
%U 45741281820,171529836218,644952073662,2430973096720,9183676536076,34766775829452,131873975875180,501121106988464
%N Number of plane trees with even number of leaves.
%C Number of Dyck n-paths with an even number of peaks (or, equivalently, odd number of valleys). - _Yu Hin Au_, Dec 07 2019
%H G. C. Greubel, <a href="/A071688/b071688.txt">Table of n, a(n) for n = 1..1000</a>
%H Yu Hin (Gary) Au, <a href="https://arxiv.org/abs/1912.00555">Some Properties and Combinatorial Implications of Weighted Small Schröder Numbers</a>, arXiv:1912.00555 [math.CO], 2019.
%H S. P. Eu, S. C. Liu and Y. N. Yeh, <a href="https://doi.org/10.1016/j.disc.2003.07.011">Odd or Even on Plane Trees</a>, Discrete Mathematics, Volume 281, Issues 1-3, 28 April 2004, Pages 189-196.
%F 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).
%F G.f.: (1/4)*(2-(1-4*x)^(1/2) + 2*x - (1+4*x^2)^(1/2))/x. - _Vladeta Jovovic_, Apr 19 2003
%F 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
%F 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
%F 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
%F 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 )
%F a(n) = (A000108(n) - 2^n * binomial(1/2, (n+1)/2))/2. - _Vladimir Reshetnikov_, Oct 03 2016
%F From _Vaclav Kotesovec_, Oct 04 2016: (Start)
%F 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).
%F a(n) ~ 2^(2*n-1)/(sqrt(Pi*n)*n).
%F (End)
%F 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
%e 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.
%p 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
%t 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)]
%t Table[(CatalanNumber[n] - 2^n Binomial[1/2, (n + 1)/2])/2, {n, 20}] (* _Vladimir Reshetnikov_, Oct 03 2016 *)
%o (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
%o (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
%o (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
%Y a(n) + A071684 = A000108: Catalan numbers.
%Y Cf. A007595.
%K easy,nonn
%O 1,3
%A _Sen-peng Eu_, Jun 23 2002
%E Edited by _Robert G. Wilson v_, Jun 25 2002
|
