The combstruct Package - Generating Functions
This worksheet is an introduction to generating functions and the combstruct package. For those not familiar with this package, there are two worksheets that give an overview of the previous version of combstruct and explain how to use it. See Introduction to the Combinatorial Structures Package and Sample Structures.
The functions, gfeqns, gfsolve, and gfseries, have been introduced to find counting generating functions of the combinatorial classes defined by grammars. Multivariate versions of these functions for use with attribute grammars are agfeqns, agfmomentsolve, and agfseries.
|
Generating Functions
|
|
Three functions are available to work with the generating functions that count the number of objects described by the grammar. Given a variable , each nonterminal in the grammar is associated with the generating function ,
,
where is the number of objects in of size .
Consider the grammar which describes necklaces with three different colors of beads.
>
|
necklace := {N=Cycle(bead), bead=Union(red,blue,green),red=Atom,blue=Atom,green=Atom};
|
The function gfeqns returns the system of generating function equations for this grammar. Note that this function does a direct translation from the grammar productions to the generating function equations, without attempting to resolve them.
>
|
gfeqns(necklace,unlabeled,z);
|
The function gfsolve solves for the explicit solutions.
>
|
gfsolve(necklace,unlabeled,z);
|
The truncated series for each generating function can also be found, using the function gfseries.
>
|
gfseries(necklace,unlabeled,z);
|
More terms are obtained by increasing the value of the global Order variable.
>
|
gfseries(necklace,unlabeled,z);
|
The function gfsolve does not always find an answer. In these cases, it returns FAIL. Consider the class of nonplane ternary trees.
>
|
sys := {G = Union(Z,Set(G,card=3))}:
|
>
|
gfsolve(sys,unlabeled,x);
|
However, gfeqns and gfseries always return answers.
>
|
gfeqns(sys,unlabeled,x);
|
>
|
gfseries(sys,unlabeled,x);
|
|
|
Multivariate Generating Functions
|
|
A multivariate generating function can be formed in two ways.
First, by associating an extra variable with any Epsilon in the grammar which has been given a nonterminal name. The extra variable counts the number of occurrences of that Epsilon. For example, if counts atoms, and marks the epsilons named in a combinatorial structure , the associated generating function is
where is the number of objects of size which have leaves. Here is a general tree where the nodes are atoms and the leaves, defined by the production leaf=Epsilon, have weight zero.
>
|
tree1 := {T=Union(L, Prod(N,Set(T))), L=Prod(leaf,Atom), leaf=Epsilon,N=Atom}:
|
Mark the leaves of this unlabeled tree.
>
|
gfeqns(tree1,unlabeled,z,[[u,leaf]]);
|
The same value can be given to more than one Epsilon name. Consider this description of arithmetic expressions in using addition and multiplication.
>
|
sys := {expression = Union(x,Prod(plus,expression,expression),Prod(times,expression,expression)), x = Atom, times = Epsilon, plus = Epsilon}:
|
You can request that the operations plus and times be marked with the variable .
>
|
Order := 10:
gfseries(sys,labeled,z,[[u,times,plus]]);
|
Or you can give them different marks.
>
|
gfseries(sys,labeled,z,[[u,times],[v,plus]]);
|
You can also associate an expression, rather than a name, to the leaves. For instance, consider the following tree.
>
|
sys := { tree=Union(Atom,tree2,tree3,tree4), tree2=Prod(node2,tree,tree), tree3=Prod(node3,tree,tree,tree), tree4=Prod(node4,tree,tree,tree,tree),node2=Epsilon,node3=Epsilon,node4=Epsilon};
|
This tree has nodes with two, three, or four branches, with atoms for leaves. Use the variable to mark the binary nodes and to mark all the internal nodes.
>
|
gfsolve(sys,labeled,z,[[u*v,node2],[v,node3,node4]]);
|
Then the coefficient of in is the number of trees with leaves that have binary nodes and internal nodes.
More generally, you can define attributes of a function, that is a function F which associates a value F(A) to a structure A. This generalizes the ideas presented in this section. For example, F(A) could equal the number of a particular type of substructure within A. The multivariate generating functions which encode counting information for structures and their attributes resemble that of A(z,u) above, where equals the number of objects A of size n for which F(A)=k.
For details on how to define and manipulate attribute grammars, see combstruct[agfeqns], combstruct[agfseries], and An Introduction to Attribute Grammars.
|
Return to Index for Example Worksheets
|