Example2-8-9-10-12-RootedTrees.mw

Examples 2.8, 2.9, 2.10, and 2.12 (Puiseux Expansions of Rooted Binary and 3-Ary Trees) 

with(gfun): 

>
 

> # Enter the algebraic equations for the generating functions under consideration
P2 := z*y^2-y+1;
P3 := z*y^3-y+1;
 

 

Typesetting:-mprintslash([P2 := `+`(`*`(`^`(y, 2), `*`(z)), `-`(y), 1)], [`+`(`*`(`^`(y, 2), `*`(z)), `-`(y), 1)])
Typesetting:-mprintslash([P3 := `+`(`*`(`^`(y, 3), `*`(z)), `-`(y), 1)], [`+`(`*`(`^`(y, 3), `*`(z)), `-`(y), 1)]) (1)
 

> # There are two Puiseix series solutions to the equation for binary trees
algeqtoseries(P2,z,y,5);
 

[series(`+`(`^`(z, -1), `-`(1), `-`(z), `-`(`*`(2, `*`(`^`(z, 2)))), `-`(`*`(5, `*`(`^`(z, 3)))))+O(`^`(z, 4)),z,4), series(`+`(1, z, `*`(2, `*`(`^`(z, 2))), `*`(5, `*`(`^`(z, 3))), `*`(14, `*`(`^`(z,... (2)
 

> # There are three Puiseix series solutions to the equation for 3-ary trees
# By default, the RootOf data structure is used to encode algebraic quantities
algeqtoseries(P3,z,y,5);
 

[series(`+`(1, z, `*`(3, `*`(`^`(z, 2))), `*`(12, `*`(`^`(z, 3))), `*`(55, `*`(`^`(z, 4))))+O(`^`(z, 5)),z,5), `+`(`/`(`*`(RootOf(`+`(`*`(`^`(_Z, 2)), `-`(1)))), `*`(`^`(z, `/`(1, 2)))), `-`(`/`(1, 2)... (3)
 

> # The allvalues command can be used to represent these expansions explicitly
allvalues(algeqtoseries(P3,z,y,5));
 

[series(`+`(1, z, `*`(3, `*`(`^`(z, 2))), `*`(12, `*`(`^`(z, 3))), `*`(55, `*`(`^`(z, 4))))+O(`^`(z, 5)),z,5), `+`(`/`(1, `*`(`^`(z, `/`(1, 2)))), `-`(`/`(1, 2)), `-`(`*`(`/`(3, 8), `*`(`^`(z, `/`(1, ...
[series(`+`(1, z, `*`(3, `*`(`^`(z, 2))), `*`(12, `*`(`^`(z, 3))), `*`(55, `*`(`^`(z, 4))))+O(`^`(z, 5)),z,5), `+`(`/`(1, `*`(`^`(z, `/`(1, 2)))), `-`(`/`(1, 2)), `-`(`*`(`/`(3, 8), `*`(`^`(z, `/`(1, ...
(4)
 

> # Compute expansions in t = 1-4z around the singular point z=1/4
allvalues(algeqtoseries(subs(z=(1-t)/4,P2),t,y,5));
 

[`+`(2, `*`(2, `*`(`^`(t, `/`(1, 2)))), `*`(2, `*`(t)), `*`(2, `*`(`^`(t, `/`(3, 2)))), `*`(2, `*`(`^`(t, 2))), O(`*`(`^`(t, `/`(5, 2)))))], [`+`(2, `-`(`*`(2, `*`(`^`(t, `/`(1, 2))))), `*`(2, `*`(t))... (5)
 

> # The algebraic curves defined by the algebraic equation for binary trees have singularities at the origin and z=1/4
{solve(discrim(P2,y))}, {solve(lcoeff(P2,y))};
 

{`/`(1, 4)}, {0} (6)
 

> # There is a branch going to infinity at 0 and two branches colliding at 1/4
plots[implicitplot](P2,z=-2..2,y=-4..4, numpoints=10^4);
 

Plot_2d
 

> # The algebraic curves defined by the algebraic equation for 3-ary trees have singularities at the origin and z=4/27
{solve(discrim(P3,y))}, {solve(lcoeff(P3,y))};
 

{0, `/`(4, 27)}, {0} (7)
 

> # There are branches going to infinity at 0 and two branches colliding at 1/4
# (One can also imagine two branches colliding "at infinity" as z goes to 0)
plots[implicitplot](P3,z=-1..1,y=-4..4, numpoints=10^4);
 

Plot_2d
 

>