Kingman derived the Ewens sampling formula for random partitions describing the genetic variation in a neutral mutation model defined by a Poisson process of mutations along lines of descent governed by a simple coalescent process and observed that similar methods could be applied to more complex models. Möhle described the recursion which determines the generalization of the Ewens sampling formula in the situation where the lines of descent are governed by a Λ-coalescent, which allows multiple mergers. Here, we show that the basic integral representation of transition rates for the Λ-coalescent is forced by sampling consistency under more general assumptions on the coalescent process. Exploiting an analogy with the theory of regenerative partition structures, we provide various characterizations of the associated partition structures in terms of discrete-time Markov chains.