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