Measures of Distinctness for Random Partitions and Compositions of an Integer

摘要: Partitions and compositions of integers are, besides their intrinsic interests, usually used as theoretical models for evolutionary processes in different contexts: statistical mechanics, theory quantum strings, populaw x tion biology, nonparametric statistics, etc.; cf. 1, 4, 8, 10, 12, 30, 49, 54 . Also parameters partitions often have natural interpretations terms w Ž characters symmetric groups; 15, 47 Thus properties statistical, algebraic, analytic, these objects received constant attention the literature. In many situations, notion ‘‘degree distinctness’’ naturally arises. The classical birthday paradox states that one needs on average ) 23 people to discover two same with probability 1r2, assuming all birth dates be equally likely; 16 coupon collector problem is similar: what expected number coupons gather before a full collection, under suitable assumptions issuing coupons? applications which only first product element, particle, ‘‘expensive’’ ‘‘cost’’ remaining reproductions negligible, study measures distinctness becomes meaningful important. distinct outcomes sequence multinomial trials occupancy has wide applications; see, example, Knuth 34 , Johnson Kotz 28 Kolchin et al. 35 Arato Benczur 5 Vitter Chen 50 sites visited by random walk plays an important role