login
Number of ordered trees with n edges such that non-leaf vertices at even (odd) level have an odd (even) number of children.
1

%I #10 Dec 27 2014 02:40:33

%S 1,1,0,2,2,6,14,30,80,191,482,1253,3178,8370,21908,57861,154262,

%T 411724,1106990,2986434,8085282,21978895,59905632,163786142,448976298,

%U 1233655230,3397615736,9376447532,25926798104,71819992609,199282159404,553834902261,1541463298372

%N Number of ordered trees with n edges such that non-leaf vertices at even (odd) level have an odd (even) number of children.

%F G.f. g is given by g = 1 + z*h/(1-z^2*h^2), where h = 1/(1-z^2*g^2). The function h(z) is the g.f. of the companion sequence A248097.

%F G.f. g is given by g*(1-z^2*g^2)^2-z^2*g = (1-z^2*g^2)^2 + z*(1-z-z^2*g^2).

%e a(4) = 2 because we have (i) the tree Y and (ii) 3 path-trees P[2] joined at their endpoints (the star-tree on 4 vertices).

%e G.f. = 1 + x + 2*x^3 + 2*x^4 + 6*x^5 + 14*x^6 + 30*x^7 + 80*x^8 + 191*x^9 + 482*x^10 + ...

%p eq := g = 1+z*h/(1-z^2*h^2): h := 1/(1-z^2*g^2): g := RootOf(eq, g): gser := series(g, z = 0, 35): seq(coeff(gser, z, n), n = 0 .. 32);

%t max=40; s[0]={}; s[n_] := s[n] = Join[s[n-1], g=Sum[a[k]*z^k, {k, 0, n}] /. s[n-1]; SolveAlways[g == Normal[Series[1+z*h/(1-z^2*h^2) /. h -> 1/(1-z^2*g^2), {z, 0, n}]], z] // First]; Table[a[n] /. s[n+1], {n, 0, max}] (* _Jean-François Alcover_, Dec 26 2014, translated and adapted from Maple *)

%Y Cf. A248097.

%K nonn

%O 0,4

%A _Emeric Deutsch_, Dec 25 2014