The combstruct Package - New Features

This worksheet is an introduction to the new features of the combstruct package. For those not already familiar with this package, there are two worksheets that give an overview of the previous version of combstruct and explain how to use it.

Several new features have been added to the combstruct package. Powersets, i.e. sets without repetition, have been implemented. The allstructs function, which generates all the elements of a given size in a combinatorial class, has been extended to accept grammar definitions, whereas previously it only worked for the pre-defined structures. Three new functions, gfeqns , gfsolve and gfseries , have been introduced to find the counting generating functions of the combinatorial classes defined by grammars.

> with(combstruct):

PowerSet

The new constructor PowerSet has been added to the description language. A PowerSet is a set without repetition, as opposed to the Set constructor which allows repetition of elements.

Here we use PowerSet to define integer partitions with distinct parts.

> sys := {L = PowerSet(Sequence(Z,card>=1)) },unlabelled;

> draw([L,sys],size=5);

> seq(count([L,sys],size=i),i=1..10);

allstructs

The allstructs command now accepts grammars as input. For example, we can generate all the alcohol molecules, , which have carbon atoms. We model a molecule by writing a grammar for an alkyl,
, which is a ternary rooted tree that moves freely in space.
molecule := {alkyl = Union(H, Prod(C, Set(alkyl, card=3))), H=Atom, C=Atom};

We find all the alkyls with 4 carbon molecules.

> allstructs([alkyl, molecule], size=4+2*4+1);

Three functions are now available to work with the generating functions that count the number of objects described by the grammar. Given a variable , each non-terminal in the grammar will be associated with the generating function ,

,

where is the number of objects in of size .

Consider the grammar which describes necklaces with three different colours 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 trying to resolve them.

> gfeqns(necklace,unlabelled,z);

The function gfsolve will try to solve for the explicit solutions.

> gfsolve(necklace,unlabelled,z);

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

> gfseries(necklace,unlabelled,z);

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

> Order := 20;

> gfseries(necklace,unlabelled,z);

The function gfsolve will not always be able to find an answer. In these cases, it returns FAIL. Consider the class of non-plane ternary trees.

> sys := {G = Union(Z,Set(G,card=3))}:

> gfsolve(sys,unlabelled,x);

However, gfeqns and gfseries will always be able to return answers.

> gfeqns(sys,unlabelled,x);

> gfseries(sys,unlabelled,x);

Multi-variate generating functions

A multi-variate generating function can be formed by associating an extra variable with any Epsilon in the grammar which has been given a non-terminal name. The extra variable counts the number of occurences of that Epsilon. For example, if counts atoms, and marks the epsilons named in a combinatorial structure , then 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}:

We can mark the leaves of this unlabelled tree.

> gfeqns(tree1,unlabelled,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}:

We can ask that the operations plus and times both be marked with the variable .

> Order := 10:
gfseries(sys,labelled,z,[[u,times,plus]]);

Or we can give them different marks.

> gfseries(sys,labelled,z,[[u,times],[v,plus]]);

We 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. We use the variable to mark the binary nodes and to mark all the internal nodes.

> gfsolve(sys,labelled,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.

>