Grammar Specification of a Combinatorial Class - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : Combinatorial Structures : combstruct/specification

Grammar Specification of a Combinatorial Class

Description

 • 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.

 Epsilon object of size 0 Atom object of size 1 (Z is a predefined atom) Union(A,B,...) disjointunion of the classes A,B, ... Prod(A,B,...) partitional product of the classes A, B, ... Set(A) all sets with repetitions whose elements are in A PowerSet(A) all sets without repetitions whose elements are in A Sequence(A) all sequences of elements of A Cycle(A) all directed cycles of elements of A Subst(A,B) 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, $\mathrm{Set}\left(A,1\le \mathrm{card}\right)$ means all nonempty sets whose elements are in $A$, $\mathrm{Sequence}\left(A,\mathrm{card}\le 3\right)$ means all sequences of at most three elements of $A$, and $\mathrm{Cycle}\left(A,\mathrm{card}=5\right)$ 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\le \mathrm{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 $\mathrm{card}\le k$ or $\mathrm{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 $\mathrm{Subst}\left(A,B\right)$, neither $A$ nor $B$ may produce objects of size 0.
 • A specification is a set of productions of the form $A=\mathrm{rhs}$, where $A$ is the name of the class being defined, and $\mathrm{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'.

 $A=\mathrm{Prod}\left(Z,\mathrm{Set}\left(A\right)\right)$ nonplane trees $B=\mathrm{Union}\left(Z,\mathrm{Prod}\left(B,B\right)\right)$ plane binary trees $C=\mathrm{Prod}\left(Z,\mathrm{Sequence}\left(C\right)\right)$ plane general trees $\mathrm{D}=\mathrm{Set}\left(\mathrm{Cycle}\left(Z\right)\right)$ permutations $F=\mathrm{Set}\left(\mathrm{Set}\left(Z,1\le \mathrm{card}\right)\right)$ set partitions $G=\mathrm{Union}\left(Z,\mathrm{Prod}\left(Z,\mathrm{Set}\left(G,\mathrm{card}=3\right)\right)\right)$ nonplane ternary trees $H=\mathrm{Union}\left(Z,\mathrm{Set}\left(H,2\le \mathrm{card}\right)\right)$ hierarchies $L=\mathrm{Set}\left(\mathrm{Set}\left(\mathrm{Set}\left(Z,1\le \mathrm{card}\right),1\le \mathrm{card}\right)\right)$ 3-balanced hierarchies $M=\mathrm{Sequence}\left(\mathrm{Set}\left(Z,1\le \mathrm{card}\right)\right)$ surjections $N=\mathrm{Set}\left(\mathrm{Cycle}\left(A\right)\right),A=\mathrm{Prod}\left(Z,\mathrm{Set}\left(A\right)\right)$ functional graphs

 When the labeling type is 'unlabeled'.

 $A=\mathrm{Set}\left(\mathrm{Sequence}\left(Z,1\le \mathrm{card}\right)\right)$ integer partition $B=\mathrm{Sequence}\left(\mathrm{Union}\left(Z,Z\right)\right)$ binary sequences $C=\mathrm{Cycle}\left(\mathrm{Set}\left(Z,1\le \mathrm{card}\right)\right)$ necklaces $\mathrm{D}=\mathrm{Prod}\left(Z,\mathrm{Set}\left(\mathrm{D}\right)\right)$ rooted unlabeled trees $F=\mathrm{Union}\left(Z,\mathrm{Set}\left(F,\mathrm{card}=2\right)\right)$ nonplane binary trees $G=\mathrm{Union}\left(Z,\mathrm{Set}\left(G,\mathrm{card}=3\right)\right)$ nonplane ternary trees $H=\mathrm{Union}\left(Z,\mathrm{Set}\left(H,2\le \mathrm{card}\right)\right)$ unlabeled hierarchies $J=\mathrm{Set}\left(\mathrm{Cycle}\left(\mathrm{D}\right)\right),\mathrm{D}=\mathrm{Prod}\left(Z,\mathrm{Set}\left(\mathrm{D}\right)\right)$ random mappings patterns $K=\mathrm{Union}\left(Z,\mathrm{Subst}\left(\mathrm{Union}\left(\mathrm{Prod}\left(Z,Z\right),\mathrm{Prod}\left(Z,Z,Z\right)\right),K\right)\right)$ 2-3 trees $L=\mathrm{PowerSet}\left(\mathrm{Sequence}\left(Z,1\le \mathrm{card}\right)\right)$ integer partitions without repetition

 • 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].

Examples

 > $\mathrm{with}\left(\mathrm{combstruct}\right):$

Generate words on two letters of the form $C=\left(aCb\right)^$.

 > $\mathrm{sys}≔\left\{C=\mathrm{Sequence}\left(\mathrm{Prod}\left(a,C,b\right)\right),a=\mathrm{Atom},b=\mathrm{Atom}\right\}:$
 > $\mathrm{word}≔\mathrm{draw}\left(\left[C,\mathrm{sys}\right],\mathrm{size}=6\right)$
 ${\mathrm{word}}{:=}{\mathrm{Sequence}}{}\left({\mathrm{Prod}}{}\left({a}{,}{\mathrm{Sequence}}{}\left({\mathrm{Prod}}{}\left({a}{,}{\mathrm{Ε}}{,}{b}\right)\right){,}{b}\right){,}{\mathrm{Prod}}{}\left({a}{,}{\mathrm{Ε}}{,}{b}\right)\right)$ (1)

If you do not need the derivation structure, remove it.

 > $\mathrm{eval}\left(\mathrm{subs}\left(\mathrm{Prod}=\left(\left(\right)→\mathrm{args}\right),\mathrm{Sequence}=\left(\left(\right)→\mathrm{args}\right),\mathrm{Ε}=\mathrm{NULL},\mathrm{word}\right)\right)$
 ${a}{,}{a}{,}{b}{,}{b}{,}{a}{,}{b}$ (2)

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.

 > $\mathrm{circuit}≔\left\{C=\mathrm{Union}\left(P,S,R\right),P=\mathrm{Set}\left(\mathrm{Union}\left(S,R\right),2\le \mathrm{card}\right),S=\mathrm{Set}\left(\mathrm{Union}\left(P,R\right),2\le \mathrm{card}\right),R=\mathrm{Atom}\right\}:$
 > $\mathrm{draw}\left(\left[C,\mathrm{circuit},\mathrm{labeled}\right],\mathrm{size}=5\right)$
 ${\mathrm{Set}}{}\left({{R}}_{{4}}{,}{\mathrm{Set}}{}\left({\mathrm{Set}}{}\left({{R}}_{{5}}{,}{\mathrm{Set}}{}\left({{R}}_{{1}}{,}{{R}}_{{2}}\right)\right){,}{{R}}_{{3}}\right)\right)$ (3)

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.

 > $\mathrm{circuit2}≔\left\{C=\mathrm{Union}\left(P,S,R\right),P=\mathrm{Prod}\left(\mathrm{par},\mathrm{Set}\left(\mathrm{Union}\left(S,R\right),2\le \mathrm{card}\right)\right),S=\mathrm{Prod}\left(\mathrm{ser},\mathrm{Set}\left(\mathrm{Union}\left(P,R\right),2\le \mathrm{card}\right)\right),R=\mathrm{Atom},\mathrm{par}=\mathrm{Ε},\mathrm{ser}=\mathrm{Ε}\right\}:$
 > $\mathrm{draw}\left(\left[C,\mathrm{circuit2},\mathrm{labeled}\right],\mathrm{size}=5\right)$
 ${\mathrm{Prod}}{}\left({\mathrm{ser}}{,}{\mathrm{Set}}{}\left({\mathrm{Prod}}{}\left({\mathrm{par}}{,}{\mathrm{Set}}{}\left({{R}}_{{5}}{,}{{R}}_{{1}}\right)\right){,}{{R}}_{{2}}{,}{\mathrm{Prod}}{}\left({\mathrm{par}}{,}{\mathrm{Set}}{}\left({{R}}_{{3}}{,}{{R}}_{{4}}\right)\right)\right)\right)$ (4)

Since Epsilon has size 0, taking the product with Epsilon does not change the number of objects of each size.