combstruct - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : Combinatorial Structures : combstruct/agfmomentsolve

combstruct

 agfmomentsolve
 solve the system of generating function equations associated with an attribute grammar

 Calling Sequence agfmomentsolve(eqns, num, neweqns)

Parameters

 eqns - set of multivariate generating function equations num - number of times to differentiate; non-negative integer neweqns - (optional) set of equations that Maple attempts to solve

Description

 • The agfmomentsolve function accepts a set of multivariate generating functions. It attempts to solve the system of generating functions where the equations are differentiated num times with respect to each variable aside from size. It then evaluates the equations  with each nonsize variable set to 1.
 The functions are returned as univariate functions.  Thus, it is important that the first variable marks size. The agfmomentsolve function is useful for finding averages and higher moments.
 • The modified equations are returned by using the third argument, neweqns. If it is specified, it is assigned to the system of equations.
 If the solving computation is intensive, you can interrupt it and recover the equations. This allows you to intervene with some manual manipulation or specialized solving methods.
 • The agfmomentsolve function relies on solutions obtained by agfmomentsolve(eqns, num-j) where $j=1..\mathrm{num}$. Thus, if these cannot be solved, fail is returned.
 • For information on how to write combstruct grammar specifications, see combstruct and combstruct[specification].

Examples

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

First, obtain a system of equations by using gfeqns or agfeqns.

The following two examples use the variable $u$ to mark the number of internal nodes in a nonplane tree.

 > $\mathrm{eqns0}≔\mathrm{agfeqns}\left(\left\{T=\mathrm{Prod}\left(Z,\mathrm{Set}\left(T\right)\right)\right\},\left\{h\left(T\right)=\mathrm{Prod}\left(0,\mathrm{Set}\left(h\left(T\right)\right)+1\right)\right\},\mathrm{labeled},z,\left[\left[u,h\right]\right]\right)$
 ${\mathrm{eqns0}}{≔}\left[{T}{}\left({z}{,}{u}\right){=}{z}{}{{ⅇ}}^{{T}{}\left({z}{,}{u}\right)}{}{u}{,}{Z}{}\left({z}{,}{u}\right){=}{z}{}{u}\right]$ (1)
 > $\mathrm{eqns1}≔\mathrm{gfeqns}\left(\left\{E=\mathrm{Ε},T=\mathrm{Prod}\left(Z,\mathrm{Prod}\left(E,\mathrm{Set}\left(T\right)\right)\right)\right\},\mathrm{labeled},z,\left[\left[u,E\right]\right]\right)$
 ${\mathrm{eqns1}}{≔}\left[{E}{}\left({z}{,}{u}\right){=}{u}{,}{T}{}\left({z}{,}{u}\right){=}{z}{}{{ⅇ}}^{{T}{}\left({z}{,}{u}\right)}{}{u}{,}{Z}{}\left({z}{,}{u}\right){=}{z}\right]$ (2)

Given the equations, it is possible to solve the generating function for the number of trees. This can be obtained from the univariate system which is obtained from the multivariate system with $u$ set to 1. Further, cumulative generating functions for the number of internal nodes in a binary tree is determined by differentiating the multivariate generating function with respect to $u$, and setting this variable to 1. That is, the value of the system that agfmomentsolve(eqns, 1) attempts to solve.

 > $\mathrm{agfmomentsolve}\left(\mathrm{eqns0},0\right)$
 $\left\{{T}{}\left({z}\right){=}{-}{\mathrm{LambertW}}{}\left({-}{z}\right){,}{Z}{}\left({z}\right){=}{z}\right\}$ (3)
 > $\mathrm{agfmomentsolve}\left(\mathrm{eqns0},1,\mathrm{new}\right)$
 $\left\{{{T}}_{{1}}{}\left({z}\right){=}{-}\frac{{{ⅇ}}^{{-}{\mathrm{LambertW}}{}\left({-}{z}\right)}}{{z}{}{{ⅇ}}^{{-}{\mathrm{LambertW}}{}\left({-}{z}\right)}{-}{1}}{,}{{T}}_{{2}}{}\left({z}\right){=}{-}\frac{{z}{}{{ⅇ}}^{{-}{\mathrm{LambertW}}{}\left({-}{z}\right)}}{{z}{}{{ⅇ}}^{{-}{\mathrm{LambertW}}{}\left({-}{z}\right)}{-}{1}}{,}{{Z}}_{{1}}{}\left({z}\right){=}{1}{,}{{Z}}_{{2}}{}\left({z}\right){=}{z}\right\}$ (4)
 > $\mathrm{new}$
 $\left[{{T}}_{{1}}{}\left({z}\right){=}{{ⅇ}}^{{-}{\mathrm{LambertW}}{}\left({-}{z}\right)}{+}{z}{}{{T}}_{{1}}{}\left({z}\right){}{{ⅇ}}^{{-}{\mathrm{LambertW}}{}\left({-}{z}\right)}{,}{{T}}_{{2}}{}\left({z}\right){=}{z}{}{{T}}_{{2}}{}\left({z}\right){}{{ⅇ}}^{{-}{\mathrm{LambertW}}{}\left({-}{z}\right)}{+}{z}{}{{ⅇ}}^{{-}{\mathrm{LambertW}}{}\left({-}{z}\right)}{,}{{Z}}_{{1}}{}\left({z}\right){=}{1}{,}{{Z}}_{{2}}{}\left({z}\right){=}{z}\right]$ (5)

The coefficient of ${z}^{n}$ of $T\left(z\right)$, $\mathrm{coeff}\left(T\left(z\right),z,n\right)$, is the number of trees with $n$ nodes, and $\mathrm{coeff}\left({T}_{2}\left(z\right),z,n\right)$ is the total sum of all trees with $n$ nodes for the number of internal nodes. The average number of internal nodes for a tree on $n$ nodes is $\frac{\mathrm{coeff}\left({T}_{2}\left(z\right),z,n\right)}{\mathrm{coeff}\left(T\left(z\right),z,n\right)}$.

 > $\mathrm{sol}≔\mathrm{agfmomentsolve}\left(\mathrm{eqns0},2\right):$
 > $\mathrm{subs}\left(\mathrm{sol},T\left[2,2\right]\left(z\right)\right)$
 $\frac{{\left({{ⅇ}}^{{-}{\mathrm{LambertW}}{}\left({-}{z}\right)}\right)}^{{2}}{}{{z}}^{{2}}{}\left({z}{}{{ⅇ}}^{{-}{\mathrm{LambertW}}{}\left({-}{z}\right)}{-}{2}\right)}{{\left({{ⅇ}}^{{-}{\mathrm{LambertW}}{}\left({-}{z}\right)}\right)}^{{3}}{}{{z}}^{{3}}{-}{3}{}{\left({{ⅇ}}^{{-}{\mathrm{LambertW}}{}\left({-}{z}\right)}\right)}^{{2}}{}{{z}}^{{2}}{+}{3}{}{z}{}{{ⅇ}}^{{-}{\mathrm{LambertW}}{}\left({-}{z}\right)}{-}{1}}$ (6)

This agfmomentsolve function yields information that can be used to compute the variance.