Grammar Specification of a Combinatorial Class
A combinatorial class is either an elementary class, or is built from simpler classes with "constructors." The elementary classes are Epsilon, which represents an object of size zero, and Atom, which represents an object of size one. The available constructors are listed in the following table.
object of size 0
object of size 1 (Z is a predefined atom)
disjointunion of the classes A,B, ...
partitional product of the classes A, B, ...
all sets with repetitions whose elements are in A
all sets without repetitions whose elements are in A
all sequences of elements of A
all directed cycles of elements of A
B-objects whose atoms are replaced by A-objects
For the constructors Set, PowerSet, Sequence, and Cycle, it is possible to add restrictions on the cardinality. For example, Set⁡A,1≤card means all nonempty sets whose elements are in A, Sequence⁡A,card≤3 means all sequences of at most three elements of A, and Cycle⁡A,card=5 means all directed cycles of five elements from A.
None of these constructors accept an object that generates Epsilon as an argument. In some cases, no cardinality restriction or k≤card with any constructor but PowerSet, such a grammar generates an infinite number of objects of size 0, whereas this system is for classes with a finite number of members of each size.
In the others, PowerSet or card≤k or card=k, while there are only a finite number of objects of size 0, the current system does not handle grammars with such Epsilon productions.
In Subst⁡A,B, neither A nor B may produce objects of size 0.
A specification is a set of productions of the form A=rhs, where A is the name of the class being defined, and rhs is an expression involving elementary classes, constructors, and other classes. For example, the following table lists specifications of some well-known combinatorial classes.
When the labeling type is 'labeled'.
plane binary trees
plane general trees
nonplane ternary trees
When the labeling type is 'unlabeled'.
rooted unlabeled trees
nonplane binary trees
random mappings patterns
integer partitions without
It is possible to use Epsilon as a way of marking certain objects without affecting their size.
There are also predefined structures, for example, combinations, built into the system. For more information, see combstruct[structures].
Generate words on two letters of the form C=a⁢C⁢b^`⁢`.
sys ≔ C=Sequence⁡Prod⁡a,C,b,a=Atom,b=Atom:
word ≔ draw⁡C,sys,size=6
If you do not need the derivation structure, remove it.
To model series and parallel circuits of resistors, a parallel circuit is made up of two or more resistors in series, and a series circuit is made up of two or more parallel circuits.
circuit ≔ C=Union⁡P,S,R,P=Set⁡Union⁡S,R,2≤card,S=Set⁡Union⁡P,R,2≤card,R=Atom:
However, you cannot tell from this answer which resistors are in series and which are in parallel. In this case, you obtain more information about the derivation by using Epsilon tags.
circuit2 ≔ C=Union⁡P,S,R,P=Prod⁡par,Set⁡Union⁡S,R,2≤card,S=Prod⁡ser,Set⁡Union⁡P,R,2≤card,R=Atom,par=Ε,ser=Ε:
Since Epsilon has size 0, taking the product with Epsilon does not change the number of objects of each size.
Download Help Document