Enumeration and random generation of accessible automata

We present a bijection between the set A(n) of deterministic and accessible automata with n states on a k-letters alphabet and some diagrams, which can themselves be represented as partitions of a set of kn + 1 elements into n non-empty subsets. This combinatorial construction shows that the asymptotic order of the cardinality of A(n) is related to the Stirling number {(kn)(n)}. Our bijective approach also yields an efficient random sampler, for the uniform distribution, of automata with n states, its complexity is O(n(3/2)), using the framework of Boltzmann samplers. (c) 2007 Elsevier BX All rights reserved.