Help on the Encyclopedia of Combinatorial Structures

This page gives informations about:

• Combinatorial structure
• Generating functions
• Graph
• Specification
• Trees

  Combinatorial Structure

A combinatorial structure is decomposable if it admits a specification in terms of unions, products, sequences, sets, and cycles, either in the labelled or in the unlabelled context. For example, a permutation of n elements is a set of cycles. These structures can be counted, generated at ramdom... with the help of the maple combstruct package.

  Generating Function

A generating function counts the objects described in the combstruct specification.
If S is a combinatorial structure, its generating function is:

    Sum {from k=0 to infinity} s_nzⁿ (ogf)
        or
    Sum {from k=0 to infinity} s_nzⁿ/n! (egf)

with s_n the number of objects in S having size n.
Ordinary generating functions (ogf) are used in the unlabelled universe, exponential generating functions (egf) in the labelled case.

  Graph:

A graph is a finite set of points called nodes or vertices connected by links called edges.
A graph is connected if every pair of nodes can be connected by a sequence of consecutive edges.

  Trees:

A tree is a connected graph without cycles.
A rooted tree has a distinguished node called the root.

  Specification:

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.

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:

• Epsilon: object of size 0
• Atom: object of size 1 (Z is a predefined atom)
• Union(A,B,...): disjoint union 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

For the constructors Set, PowerSet, Sequence, and Cycle, it is possible to add some restrictions on the cardinality: for example, Set(A,card>=1) means all non-empty 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 will accept an object that generates Epsilon as an argument. In some cases (no cardinality restriction or card>=k with any constructor but PowerSet), such a grammar would generate 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 cases of 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.

For example, below are the specifications of some well-known combinatorial classes.
When the labelling type is labelled:

• A = Prod(Z,Set(A)): non plane trees
• B = Union(Z,Prod(B,B)): plane binary trees
• C = Prod(Z,Sequence(C)): plane general trees
• D = Set(Cycle(Z)): permutations
• F = Set(Set(Z,card>=1)): set partitions
• G = Union(Z,Prod(Z,Set(G,card=3))): non plane ternary trees
• H = Union(Z,Set(H,card>=2)): hierarchies
• L = Set(Set(Set(Z,card>=1),card>=1)): 3-balanced hierarchies
• M = Sequence(Set(Z,card>=1)): surjections
• N = Set(Cycle(A)), A=Prod(Z,Set(A)): functional graphs

When the labelling type is unlabelled:

• A = Set(Sequence(Z,card>=1)): integer partition,
• B = Sequence(Union(Z,Z)): binary sequences
• C = Cycle(Set(Z,card>=1)): necklaces
• D = Prod(Z,Set(D)): rooted unlabelled trees
• F = Union(Z,Set(F,card=2)): nonplane binary trees
• G = Union(Z,Set(G,card=3)): nonplane ternary trees
• H = Union(Z,Set(H,card>=2)): unlabelled hierarchies
• J = Set(Cycle(D)), D=Prod(Z,Set(D)): random mappings patterns
• K = Union(Z,Subst(Union(Prod(Z,Z),Prod(Z,Z,Z)),K)): 2-3 trees
• L = PowerSet(Sequence(Z,card>=1)): integer partitions without repetition

It is possible to use Epsilon as a way of marking certain objects without affecting their size. Refer to the examples.