Random generation of trees acid other combinatorial objects

In this paper, we present a general method for the random generation of som e classes of combinatorial objects. Our basic idea is to translate ECO meth od (Enumerating Combinatorial Objects) from a method for the enumeration of combinatorial objects into a random generation method. The algorithms we i llustrate are based on the concepts of succession rule and generating tree: the former is a law that predicts the combinatorial object class growth ac cording to a given parameter. The generating tree related to a given succes sion rule is a particular labelled plane tree that represents the rule in a n extensive way. Each node of a generating tree can also be seen as a parti cular combinatorial object and so a random path in the generating tree coin cides with the random generation of that combinatorial object. The generati on is uniform if we take the probability of each branch to be selected into account when the path is generated. We also give the formulae evaluating c omplexity. Finally, we take the class of m-ary trees into consideration in order to illustrate our general method. In this case, the average time comp lexity of the generating algorithm can be estimated as O(mn). (C) 1999 Else vier Science B.V. All rights reserved.