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

1, 1, 0, 2, 2, 6, 14, 30, 80, 191, 482, 1253, 3178, 8370, 21908, 57861, 154262, 411724, 1106990, 2986434, 8085282, 21978895, 59905632, 163786142, 448976298, 1233655230, 3397615736, 9376447532, 25926798104, 71819992609, 199282159404, 553834902261, 1541463298372

Offset

0,4

Links

Table of n, a(n) for n=0..32.

Formula

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.

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

Example

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).
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 + ...

Maple

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

Mathematica

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

Crossrefs

Cf. A248097.

Sequence in context: A051890 A071109 A005310 * A002203 A300863 A278331

Adjacent sequences: A248093 A248094 A248095 * A248097 A248098 A248099

Keyword

nonn

Author

Emeric Deutsch, Dec 25 2014

Status

approved