Grammar Specification of a Combinatorial Class - Maple Help

Online Help

All Products    Maple    MapleSim


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

Grammar Specification of a Combinatorial Class

 

Description

Examples

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, SetA,1card means all nonempty sets whose elements are in A, SequenceA,card3 means all sequences of at most three elements of A, and CycleA,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 kcard 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 cardk 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 SubstA,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'.

 

 

A=ProdZ,SetA

nonplane trees

B=UnionZ,ProdB,B

plane binary trees

C=ProdZ,SequenceC

plane general trees

D=SetCycleZ

permutations

F=SetSetZ,1card

set partitions

G=UnionZ,ProdZ,SetG,card=3

nonplane ternary trees

H=UnionZ,SetH,2card

hierarchies

L=SetSetSetZ,1card,1card

3-balanced hierarchies

M=SequenceSetZ,1card

surjections

N=SetCycleA,A=ProdZ,SetA

functional graphs

 

 

  

When the labeling type is 'unlabeled'.

 

 

A=SetSequenceZ,1card

integer partition

B=SequenceUnionZ,Z

binary sequences

C=CycleSetZ,1card

necklaces

D=ProdZ,SetD

rooted unlabeled trees

F=UnionZ,SetF,card=2

nonplane binary trees

G=UnionZ,SetG,card=3

nonplane ternary trees

H=UnionZ,SetH,2card

unlabeled hierarchies

J=SetCycleD,D=ProdZ,SetD

random mappings patterns

K=UnionZ,SubstUnionProdZ,Z,ProdZ,Z,Z,K

2-3 trees

L=PowerSetSequenceZ,1card

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

withcombstruct:

Generate words on two letters of the form C=aCb^``.

sysC=SequenceProda,C,b,a=Atom,b=Atom:

worddrawC,sys,size=6

word:=SequenceProda,SequenceProda,Ε,b,b,Proda,Ε,b

(1)

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

evalsubsProd=→args,Sequence=→args,Ε=NULL,word

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.

circuitC=UnionP,S,R,P=SetUnionS,R,2card,S=SetUnionP,R,2card,R=Atom:

drawC,circuit,labeled,size=5

SetR4,SetSetR5,SetR1,R2,R3

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

circuit2C=UnionP,S,R,P=Prodpar,SetUnionS,R,2card,S=Prodser,SetUnionP,R,2card,R=Atom,par=Ε,ser=Ε:

drawC,circuit2,labeled,size=5

Prodser,SetProdpar,SetR5,R1,R2,Prodpar,SetR3,R4

(4)

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

See Also

combstruct

combstruct[structures]

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam