 |  |  | Combinatorial species theory |
Combinatorial species theory
During the last 15 years the theory of combinatorial species was
mainly developed in Montreal, Canada.
It is dealing both with labelled and unlabelled
structures, especially it allows to compute generating function for the
numbers of various labelled and unlabelled structures. Let's have a short
look at Joyals proof [30]
of Cayle's theorem that there are exactly
nn-2 labelled trees on n points. In order to prove this theorem with a
species theoretic method we start with endofunctions on an n-set
X, which are functions from X to X. Clearly there are exactly nn
such endofunctions. When drawing the graph of an endofunction we realize that
there are two different kinds of points, namely points lying on a cycle and
points not lying on a cycle of the endofunction. If we identify the points
lying on a cycle with roots of rooted trees (the rooted tree consists of the
root and all those points which will be mapped onto the root by an arbitrary
iteration of the endofunction and which are not lying on a cycle) then
endofunctions can be considered as permutations of rooted trees.
Since we
only want to enumerate them we can replace "permutations" with "linear
orders" and we derive the following identity which holds for generating
functions as well:
Permutations of rooted trees are linear orders of rooted trees.
Furthermore we realize that linear orders of rooted trees correspond to
twice punctuated trees. (Punctuation of a tree means to distinguish one point
of the tree from all the other points.) Since we can distinguish any of the
n points of a tree (to be the smallest and the largest element in the
linear order) there are n2 possibilities to punctuate a tree twice.
Now we derive that
n2· number of trees =
number of total orderings of rooted trees =
number of permutations of rooted trees =
number of endofunctions =nn.
This is a typical combinatorial proof since it reformulates the problem in
various combinatorial situations such that we finally realize that the
proposition is true. This article by Joyal [30]
marks the starting point of
combinatorial species theory. Since that time this theory developed into many
directions. So far there is only one complete monograph [4]
on species theory
which will now be translated into English. It has a more or less complete
bibliography on species theory. In addition to this one can find an
introduction to species theory in A. Kerber's book [32] on algebraic
combinatorics.
So far most of the results obtained in species theory are formulated for
generating functions, so these results solve enumerative problems using for
instance generating functions for all labelled species, type counting
functions, cycle index series and asymmetric series. Now it would be
interesting to reformulate these results for the construction of discrete
structures.
It should be possible to develop a data structure in a computer
algebra system which allows to handle combinatorial species. It would be
necessary to implement some standard types of species, like the empty
species, the species empty set, the species singleton, the species set, the species permutations, the species linear orders and some
standard operators for species like species sum, species
product, plethysm of species, derivation of species, punctuation of species and so on, which are combinatorial constructions
describing the corresponding action on generating functions. Using this
machinery it would be possible for instance
to construct all endofunctions as permutations
of rooted trees. Of course we should have routines both for labelled and
unlabelled structures.
It is planned to incorporate this package on constructive species theory
into SYMMETRICA, so it will be available to the public. This package would
open interesting new possibilities for the construction-approach under finite
group actions.
harald.fripertinger@kfunigraz.ac.at,
last changed: January 23, 2001
| | | Combinatorial species theory |