login
A071684
Number of plane trees with n edges and having an odd number of leaves.
2
1, 1, 2, 7, 22, 66, 212, 715, 2438, 8398, 29372, 104006, 371516, 1337220, 4847208, 17678835, 64823110, 238819350, 883629164, 3282060210, 12233141908, 45741281820, 171529777432, 644952073662, 2430973304732, 9183676536076
OFFSET
1,3
COMMENTS
Narayana transform (A001263) of [1, 0, 1, 0, 1, 0, 1, ...]. Example: a(4) = 7 = (1, 6, 6, 1) dot (1, 0, 1, 0) = (1 + 0 + 6 + 0). - Gary W. Adamson, Jan 04 2008
LINKS
S. P. Eu, S. C. Liu and Y. N. Yeh, Odd or Even on Plane Trees, Discrete Math. 281 (2004), 189-196.
FORMULA
a(2*n) = (1/(4*n + 2))*binomial(4*n, 2*n);
a(2*n-1) = (1/(4*n))*binomial(4*n-2, 2*n-1) - (-1)^n*(1/(2*n))*binomial(2*n-2, n-1), with n>0.
G.f.: (1/4)*((1+4*x^2)^(1/2) - (1-4*x)^(1/2)-2*x)/x. - Vladeta Jovovic, Apr 19 2003
a(0)=0; a(n) = Sum_{k = 0..floor(n/2)} (1/n)*C(n,2*k+1)*C(n,2*k) for n>0. - Paul Barry, Jan 25 2007
a(n) = Sum_{k=1..n} (1/n)*C(n,k)*C(n,k-1)*(1-(-1)^k)/2. - Paul Barry, Dec 16 2008
Conjecture: n*(n+1)*(10*n-37)*a(n) + 2*n*(5*n^2-42*n+91)*a(n-1) + 4*(-40*n^3+270*n^2-560*n+357)*a(n-2) + 8*(n-3)*(5*n^2-42*n+91)*a(n-3) - 16*(n-4)*(25*n-51)*(2*n-7)*a(n-4) = 0. - R. J. Mathar, Jul 05 2018
a(n) = (A000108(n) + 2^n * binomial(1/2, (n+1)/2))/2. - Vladimir Reshetnikov, Oct 03 2016
32*n*(2*n+1)*a(n) - 48*(n+2)*(n+1)*a(n+1) + 8*(n^2-n-9)*a(n+2) - 4*(2*n^2+10*n+9)*a(n+3) - 2*(n+5)*(n+6)*a(n+4) + (n+5)*(n+6)*a(n+5) = 0. - Robert Israel, Jul 05 2018
EXAMPLE
a(3)=2 because among the 5 plane 3-trees there are 2 trees with odd number of leaves; a(4)=7 because among the 14 plane 4-trees there are 7 trees with odd number of leaves.
MAPLE
G:=((1+4*x^2)^(1/2)-(1-4*x)^(1/2)-2*x)/4/x: Gser:=series(G, x=0, 30): seq(coeff(Gser, x, n), n=1..26); # Emeric Deutsch, Feb 17 2007
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 *)
CROSSREFS
a(n) + A071688 = A000108: Catalan numbers.
Sequence in context: A084264 A333678 A088211 * A290917 A060816 A171847
KEYWORD
nonn,easy
AUTHOR
Sen-peng Eu, Jun 23 2002
EXTENSIONS
Edited by Robert G. Wilson v, Jun 25 2002
STATUS
approved