gfsolve - Maple Help

combstruct

 gfsolve
 solve the system of generating functions associated with a grammar

 Calling Sequence gfsolve(spec, typ, var, tags)

Parameters

 spec - combinatorial specification typ - labeling type; 'labeled' or 'unlabeled' var - variable to use in the generating functions tags - (optional) list of lists; each list contains a variable tag followed by the Epsilon nonterminal name(s) associated with that tag

Description

 • The gfsolve function returns a set containing the generating functions which count the objects described in the specification.
 Each nonterminal $A$, has an associated generating function $A\left(z\right)$, found by solving the system of generating function equations associated with the specification. If it cannot solve the system, it returns FAIL.
 • If the objects are labeled, exponential generating functions are produced. If the objects are unlabeled, ordinary generating functions are used.
 • Objects can be marked (tagged) by forming the product of that object with a named Epsilon and associating a tag with that Epsilon. If the tag is a variable name, the resulting generating function has an extra variable that marks that object. The same tag can be associated with more than one Epsilon name. The tag does not need to be a variable.
 • For information on how to write specifications, see combstruct and combstruct[specification].

Examples

 > $\mathrm{with}\left(\mathrm{combstruct}\right):$

An example of a labeled binary tree.

 > $\mathrm{tree}≔\left\{L=\mathrm{Atom},N=\mathrm{Atom},T=\mathrm{Union}\left(L,\mathrm{Prod}\left(N,T,T\right)\right)\right\}:$
 > $\mathrm{gfsolve}\left(\mathrm{tree},\mathrm{labeled},z\right)$
 $\left\{{L}{}\left({z}\right){=}{z}{,}{N}{}\left({z}\right){=}{z}{,}{T}{}\left({z}\right){=}{-}\frac{{-}{1}{+}\sqrt{{-}{4}{}{{z}}^{{2}}{+}{1}}}{{2}{}{z}}\right\}$ (1)

Nonplane ternary trees.  Mark the leaf nodes of an unlabeled general tree.

 > $\mathrm{ternary_tree}≔\left\{G=\mathrm{Union}\left(Z,\mathrm{Prod}\left(Z,\mathrm{Set}\left(G,\mathrm{card}=3\right)\right)\right)\right\},\mathrm{labeled}:$
 > $\mathrm{gfsolve}\left(\mathrm{ternary_tree},x\right)$
 $\left\{{G}{}\left({x}\right){=}{-}\frac{{\left(\left({-}{3}{}{x}{+}\sqrt{\frac{{9}{}{{x}}^{{3}}{-}{8}}{{x}}}\right){}{{x}}^{{2}}\right)}^{{1}}{{3}}}}{{2}{}{x}}{-}\frac{{1}}{{\left(\left({-}{3}{}{x}{+}\sqrt{\frac{{9}{}{{x}}^{{3}}{-}{8}}{{x}}}\right){}{{x}}^{{2}}\right)}^{{1}}{{3}}}}{-}\frac{{I}{}\sqrt{{3}}{}\left(\frac{{\left(\left({-}{3}{}{x}{+}\sqrt{\frac{{9}{}{{x}}^{{3}}{-}{8}}{{x}}}\right){}{{x}}^{{2}}\right)}^{{1}}{{3}}}}{{x}}{-}\frac{{2}}{{\left(\left({-}{3}{}{x}{+}\sqrt{\frac{{9}{}{{x}}^{{3}}{-}{8}}{{x}}}\right){}{{x}}^{{2}}\right)}^{{1}}{{3}}}}\right)}{{2}}{,}{Z}{}\left({x}\right){=}{x}\right\}$ (2)

Mark the leaf nodes of an labeled general tree.

 > $\mathrm{tree1}≔\left\{L=\mathrm{Prod}\left(\mathrm{leaf},\mathrm{Atom}\right),N=\mathrm{Atom},T=\mathrm{Union}\left(L,\mathrm{Prod}\left(N,\mathrm{Set}\left(T\right)\right)\right),\mathrm{leaf}=\mathrm{Ε}\right\}:$
 > $\mathrm{gfsolve}\left(\mathrm{tree1},\mathrm{labeled},z,\left[\left[u,\mathrm{leaf}\right]\right]\right)$
 $\left\{{L}{}\left({z}{,}{u}\right){=}{u}{}{z}{,}{N}{}\left({z}{,}{u}\right){=}{z}{,}{T}{}\left({z}{,}{u}\right){=}{u}{}{z}{-}{\mathrm{LambertW}}{}\left({-}{z}{}{{ⅇ}}^{{u}{}{z}}\right){,}{\mathrm{leaf}}{}\left({z}{,}{u}\right){=}{u}\right\}$ (3)