Title | ||
---|---|---|
A Poisson * Geometric Convolution Law for the Number of Components in Unlabelled Combinatorial Structures |
Abstract | ||
---|---|---|
Given a class of combinatorial structures 𝒞, we consider the quantity N(n, m), the number of multiset constructions 𝒫 (of 𝒞) of size n having exactly m 𝒞-components. Under general analytic conditions on the generating function of 𝒞, we derive precise asymptotic estimates for N(n, m), as n→∞ and m varies through all possible values (in general 1≤m≤n). In particular, we show that the number of 𝒞-components in a random (assuming a uniform probability measure) 𝒫-structure of size n obeys asymptotically a convolution law of the Poisson and the geometric distributions. Applications of the results include random mapping patterns, polynomials in finite fields, parameters in additive arithmetical semigroups, etc. This work develops the ‘additive’ counterpart of our previous work on the distribution of the number of prime factors of an integer [20]. |
Year | DOI | Venue |
---|---|---|
1998 | 10.1017/S0963548397003295 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
unlabelled combinatorial structures,random mapping pattern,general analytic condition,finite field,convolution law,quantity n,additive arithmetical semigroups,size n obeys,previous work,size n,geometric convolution law,combinatorial structure,generating function,geometric distribution,probability measure | Discrete mathematics,Generating function,Arithmetic function,Finite field,Combinatorics,Convolution,Multiset,Probability measure,Prime factor,Poisson distribution,Law,Mathematics | Journal |
Volume | Issue | ISSN |
7 | 1 | 0963-5483 |
Citations | PageRank | References |
1 | 0.40 | 8 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hsien-Kuei Hwang | 1 | 365 | 38.02 |