Three functions are available to work with the generating functions that count the number of objects described by the grammar. Given a variable $z$, each nonterminal $A$ in the grammar is associated with the generating function $A\left(z\right)$,

$A\left(z\right)\=\sum _{n\=0}^{\infty }{a}_n{z}^n$,

where $a_n$ is the number of objects in $A$ of size $n$.

Consider the grammar which describes necklaces with three different colors of beads.

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.

The function gfsolve solves for the explicit solutions.

The truncated series for each generating function can also be found, using the function gfseries.

More terms are obtained by increasing the value of the global Order variable.

The function gfsolve does not always find an answer.  In these cases, it returns FAIL.  Consider the class of nonplane ternary trees.

However, gfeqns and gfseries always return answers.

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 $z$ counts atoms, and $u$ marks the epsilons named $\mathrm{leaf}$ in a combinatorial structure $A$, the associated generating function is

$A\left(z\,u\right)\=\sum _{n\=0}^{\infty }\left(\sum _{k\=0}^{\infty }{a}_{n\,k}{u}^k\right)z^n$

where $a_{n\,k}$ is the number of objects of size $n$ which have $k$ leaves. Here is a general tree where the nodes are atoms and the leaves, defined by the production leaf=Epsilon, have weight zero.

Mark the leaves of this unlabeled tree.

The same value can be given to more than one Epsilon name.  Consider this description of arithmetic expressions in $x$ using addition and multiplication.

You can request that the operations plus and times be marked with the variable $u$.

Or you can give them different marks.

You can also associate an expression, rather than a name, to the leaves. For instance, consider the following tree.

This tree has nodes with two, three, or four branches, with atoms for leaves. Use the variable $u$ to mark the binary nodes and $v$ to mark all the internal nodes.

Then the coefficient of $u^p{v}^q{z}^n$ in $\mathrm{tree}\left(v\,u\,z\right)$ is the number of trees with $n$ leaves that have $p$ binary nodes and $q$ 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  $a_{n\,k}$ 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.

An Introduction to Attribute Grammars, combstruct, combstruct[agfeqns], combstruct[agfmomentsolve], combstruct[agfseries], combstruct[gfeqns], combstruct[gfseries], combstruct[gfsolve], Introduction to the Combinatorial Structures Package, Sample Structures