combstruct - Maple Programming Help

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

combstruct

 agfeqns
 find the system of generating function equations associated with an attribute grammar
 agfseries
 find the series solution of a system of generating function equations associated with an attribute grammar

 Calling Sequence agfeqns(spec, a_spec, typ, var, att_list) agfseries(spec, a_spec, typ, var, att_list)

Parameters

 spec - combinatorial specification a_spec - specification of attribute grammar associated with spec typ - labeling type; 'labeled' or 'unlabeled' var - main (size) variable in the generating function att_list - list of lists associating attribute names with variables

Description

 • These functions, agfeqns and agfseries, form the attribute grammar analogues to combstruct[gfeqns], and combstruct[gfseries].  For details on specifications, see combstruct and combstruct[specification].
 • These functions involve multivariate generating function equations which count the objects, as described in the specification spec, and properties of the structures, as defined in the attribute grammar, a_spec.
 Each nonterminal in the grammar is associated with a generating function which is named with the name of the structure. For example, $A\left(z,u\right)$ would be a generating function for $A$.  These two functions, agfeqns and agfseries, determine the equations in terms of other nonterminals and specify the series for the generating functions, respectively.
 • For example, in an unlabeled system with structure $A$ and attributes ${f}_{1}$ and ${f}_{2}$, the multivariate generating function is defined as $A\left(z,{q}_{1},{q}_{2}\right)=\sum _{A}\phantom{\rule[-0.0ex]{5.0px}{0.0ex}}{z}^{\left|a\right|}{q}_{1}^{f[1]\left(a\right)}{q}_{2}^{f[2]\left(a\right)}$.
 • Any number of attributes is allowable, but no user-defined attribute can be marked by the parameter var.
 • If the objects are labeled, the exponential generating functions are produced. If the objects are unlabeled, ordinary generating functions are used.
 • The attribute, size, is used for the property pertaining to the number of atoms. It can be referenced in another attribute, but not redefined.
 • If no rule is defined for a given attribute structure pair, a default recursive rule is used. For example, $A=\mathrm{Union}\left(B,C,E\right)$ and the attribute $f$ imply a default attribute specification of $f\left(A\right)=\mathrm{Union}\left(f\left(B\right),f\left(C\right),f\left(E\right)\right)$.
 • Each attribute must be marked by a single, unique variable.

Examples

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

For example, a labeled binary tree is a node or a node and two subtrees.

 > $\mathrm{tree}≔\left\{T=\mathrm{Union}\left(N,\mathrm{Prod}\left(N,T,T\right)\right),N=\mathrm{Atom}\right\}:$

One can use attributes to count the number of leaves.

 > $\mathrm{l_tree}≔\left\{\mathrm{leaf}\left(T\right)=\mathrm{Union}\left(1,\mathrm{Prod}\left(0,\mathrm{leaf}\left(T\right),\mathrm{leaf}\left(T\right)\right)\right)\right\}:$
 > $\mathrm{agfeqns}\left(\mathrm{tree},\mathrm{l_tree},\mathrm{unlabeled},z,\left[\left[u,\mathrm{leaf}\right]\right]\right)$
 $\left[{N}{}\left({z}{,}{u}\right){=}{z}{}{u}{,}{T}{}\left({z}{,}{u}\right){=}{z}{}{u}{+}{z}{}{{T}{}\left({z}{,}{u}\right)}^{{2}}\right]$ (1)

For example, the series up to order 10 indicates that there are five trees with 7 nodes and 4 leaves.

 > $\mathrm{Order}≔10:$$\mathrm{agfseries}\left(\mathrm{tree},\mathrm{l_tree},\mathrm{unlabeled},z,\left[\left[u,\mathrm{leaf}\right]\right]\right)$
 ${\mathrm{table}}\left(\left[{N}{}\left({z}{,}{u}\right){=}{u}{}{z}{,}{T}{}\left({z}{,}{u}\right){=}{u}{}{z}{+}{{u}}^{{2}}{}{{z}}^{{3}}{+}{2}{}{{u}}^{{3}}{}{{z}}^{{5}}{+}{5}{}{{u}}^{{4}}{}{{z}}^{{7}}{+}{14}{}{{u}}^{{5}}{}{{z}}^{{9}}{+}{\mathrm{O}}\left({{z}}^{{11}}\right)\right]\right)$ (2)

The internal path length, or sum of distances from nodes to the root, can be defined recursively.

 > $\mathrm{pl_tree}≔\left\{\mathrm{path}\left(T\right)=\mathrm{Union}\left(0,\mathrm{Prod}\left(0,\mathrm{size}\left(T\right)+\mathrm{path}\left(T\right),\mathrm{size}\left(T\right)+\mathrm{path}\left(T\right)\right)\right)\right\}:$
 > $\mathrm{agfeqns}\left(\mathrm{tree},\mathrm{pl_tree},\mathrm{unlabeled},z,\left[\left[u,\mathrm{path}\right]\right]\right)$
 $\left[{N}{}\left({z}{,}{u}\right){=}{z}{}{u}{,}{T}{}\left({z}{,}{u}\right){=}{z}{+}{z}{}{{T}{}\left({z}{}{u}{,}{u}\right)}^{{2}}\right]$ (3)

This system can be solved and the average values attained.