Enumeration of m-ary cacti

The purpose of this paper is to enumerate various classes of cyclically col ored m-gonal plane cacti, called m-ary cacti. This combinatorial problem is motivated by the topological classification of complex polynomials having at most rn critical values. studied by Zvonkin and others. We obtain explic it formulae for both labelled and unlabelled m-ary cacti, according to (i) the number of polygons, (ii) the vertex-color distribution. (iii) the verte x-degree distribution of each color. We also enumerate m-ary cacti accordin g to the order of their automorphism group. Using a generalization of Otter 's formula, we express the species of m-ary cacti in terms of roared and of pointed cacti. A variant of the,,m-dimensional Lagrange inversion is then used to enumerate these structures. The method of Liskovets for the enumera tion of unrooted planar maps can also be adapted to m-ani Cacti. (C) 2000 A cademic Press.