Combinatorial Structures Package - Sample Structures
The combstruct package is used to define, count, and generate combinatorial structures. A combinatorial class is defined by writing a grammar specification that describes it. In this way, an extensive collection of different classes may be defined. For example, the system applies to all regular and context-free grammars, grammars to define binary trees, plane general trees, necklaces, functional graphs, expression trees, etcetera. Given a grammar specification, the system creates a dedicated counting procedure for that structure. The number of objects of size n are counted in worst-case O(n^2) arithmetic operations. This bound is independent of the combinatorial class. In the same way, an object of size n is generated uniformly at random in worst-case O(n log(n)) arithmetic operations. Again, this bound applies to all structures. O(n log(n)) is the best known bound for many combinatorial classes. This worksheet explores, through examples, some of the uses of the combstruct package. A companion worksheet, Introduction to the Combinatorial Structures Package, explains in detail how to write a grammar specification, the predefined structures available in combstruct, and the use of the various functions.
with(combstruct):
General Trees
The combstruct package can be used to analyze certain aspects of a combinatorial structure. By repeatedly generating random examples of a structure, you can learn about its average behavior. For example, you are interested in the average height of a general tree. You can use combstruct to model such trees and analyze the results. First, write a grammar specification that describes a tree. A tree consists of a root node, and zero or more children that are also trees.
Tree := {T=Prod(Z, Set(T))}:
Count and generate general trees.
seq(count([T,Tree],size=i),i=1..20);
draw([T,Tree],size=5);
Now write a small procedure that takes a tree and returns its height.
height := proc(t) local h; if t=Prod(Z,Epsilon) then h := 1 else h := 1+ max(op(map(procname, op(2,t)))) fi; if length(t) < 100 then # store small values in the remember table height(t) := h; fi; h; end:
t := draw([T,Tree],size=5);
height(t);
Next generate many trees of size 100. For each tree, calculate its height.
treesize := 100:
numtrees := 200:
heights := array(sparse, 1..treesize):
to numtrees do h := height(draw([T,Tree],size=treesize)): heights[h] := heights[h] + 1: od:
In order to get a reasonably smooth curve, group the heights into intervals of 4.
groupedheights := array(sparse,1..treesize/4):
for i to treesize do groupedheights[iquo(i-1,4)+1] := groupedheights[iquo(i-1,4)+1]+heights[i]od:
Plot the distribution of heights of our randomly generated trees.
plot([seq([i*4-2, groupedheights[i]], i=1..treesize/4)], title=`distribution of heights of trees of size 100`);
Connected Functional Graphs
Every function that takes distinct elements {1, ..., n} into itself has a corresponding graph. Points on the graph are either cyclic, meaning that some iteration of the function takes that element back onto itself, or noncyclic. The set of points that go to the same cyclic point is a general tree. A connected functional graph is a functional graph which has one component. Such a graph corresponds to a function which, for any two elements, iterating the function on the first element a certain number of times reaches the same result as iterating the function on the second element a (possibly different) number of times. In other words, a function f such that, for every x and y in {1,..., n}, there exists a pair of non-negative integers (i,j) such that f^(i)(x) = f^(j)(y). Count the number of all such functions on n elements by counting the number of connected functional graphs.
fungraph := {F=Cycle(tree), tree=Prod(Z,Set(tree))}:
count([F, fungraph, labeled], size=40);
seq(count([F, fungraph, labeled], size=i), i=1..10);
You can also generate examples of functions with this property.
draw([F, fungraph, labeled], size=11);
Alcohols
You can model alcohol molecules, C_n H_{2n+1} OH, using combstruct. Write a grammar for an alkyl, C_n H_{2n+1}, 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}:
count([alkyl, molecule], size=6+2*6+1);
Thus, you see that there are 17 different alcohol molecules with 6 carbon atoms. The following is an example of one.
draw([alkyl, molecule], size=6+6*2+1);
Necklaces
A necklace is a classical structure from combinatory. It is a cycle containing beads of different colors. Necklaces are particularly difficult to count because of the symmetries involved, since beads of the same color are indistinguishable, and knowing how many necklaces there are of size n does not help you determine how many necklaces there are of size n+1, since the symmetries change for each size depending on how that integer factors. Define a necklace that has three different colors of beads.
necklace := {N=Cycle(bead), bead=Union(red,blue,green),red=Atom,blue=Atom,green=Atom}:
seq(count([N, necklace], size=i), i=1..15);
draw([N, necklace], size=10);
You can also create necklaces of necklaces.
neckneck := {NN=Cycle(Cycle(bead)), bead=Union(red,blue,green), red=Atom, blue=Atom,green=Atom}:
count([NN,neckneck], size=80);
draw([NN,neckneck], size=15);
Involutions
An involution is a permutation of elements that is its own inverse. Such a permutation must decompose into cycles of length one or two. You can count the involutions on n distinct elements.
involution := {inv = Set(Cycle(Z, card <= 2))}:
count([inv, involution,labeled], size=12);
You can compare this with the total number of permutations on 12 elements. Use one of the predefined structures of combstruct.
count(Permutation(12));
The following is one of the involutions on 12 elements.
draw([inv, involution,labeled], size=12);
See Also
combstruct, combstruct[agfeqns], combstruct[allstructs], combstruct[count], combstruct[draw], combstruct[finished], combstruct[iterstructs], combstruct[nextstruct], combstruct[specification], combstruct[structures], Generating Functions, Introduction to the Combinatorial Structures Package
Return to Index for Example Worksheets
Download Help Document
