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):


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;

[Maple Math]

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

[Maple Math]

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

[Maple Math]


The allstructs command now accepts grammars as input. For example, we can generate all the alcohol molecules, [Maple Math] , which have [Maple Math] carbon atoms. We model a molecule by writing a grammar for an alkyl,
[Maple Math] , 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};

[Maple Math] [Maple Math]

We find all the alkyls with 4 carbon molecules.

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

[Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math]

Generating functions

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

[Maple Math] ,

where [Maple Math] is the number of objects in [Maple Math] of size [Maple Math] .

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};

[Maple Math] [Maple Math]

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);

[Maple Math] [Maple Math]

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

> gfsolve(necklace,unlabelled,z);

[Maple Math] [Maple Math]

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

> gfseries(necklace,unlabelled,z);

[Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math]

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

> Order := 20;

[Maple Math]

> gfseries(necklace,unlabelled,z);

[Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math]

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);

[Maple Math]

gfeqns and gfseries will always be able to return answers.

> gfeqns(sys,unlabelled,x);

[Maple Math]

> gfseries(sys,unlabelled,x);

[Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math]

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 [Maple Math] counts atoms, and [Maple Math] marks the epsilons named [Maple Math] in a combinatorial structure [Maple Math] , then the associated generating function is

[Maple Math]

where [Maple Math] is the number of objects of size [Maple Math] which have [Maple Math] 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]]);

[Maple Math] [Maple Math]

The same value can be given to more than one Epsilon name. Consider this description of arithmetic expressions in
[Maple Math] 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
[Maple Math] .

> Order := 10:

[Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math]

Or we can give them different marks.

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

[Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math]

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};

[Maple Math] [Maple Math] [Maple Math]

This tree has nodes with two, three or four branches, with atoms for leaves. We use the variable
[Maple Math] to mark the binary nodes and [Maple Math] to mark all the internal nodes.

> gfsolve(sys,labelled,z,[[u*v,node2],[v,node3,node4]]);

[Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math] [Maple Math]

Then the coefficient of [Maple Math] in [Maple Math] is the number of trees with [Maple Math] leaves that have [Maple Math] binary nodes and [Maple Math] internal nodes.