A071684 Number of plane trees with n edges and having an odd number of leaves.

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

Author

Sen-peng Eu, Jun 23 2002

Keywords

• nonn
• easy

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

Examples

			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.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..1668
• Yu Hin 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 Math. 281 (2004), 189-196.

Crossrefs

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

Cf. A001263, A007595.

Programs

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 *)

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

Extensions

Edited by Robert G. Wilson v, Jun 25 2002