Expansive Multisets: Asymptotic Enumeration

Consider a non-negative sequence $c_n = h(n) \cdot n^{α-1} \cdot ρ^{-n}$, where $h$ is slowly varying, $α>0$, $0<ρ<1$ and $n\in\mathbb{N}$. We investigate the coefficients of $G(x,y) = \prod_{k\ge1}(1-x^ky)^{-c_k}$, which is the bivariate generating series of the multiset construction of combinatorial objects. By a powerful blend of probabilistic methods based on the Boltzmann model and analytic techniques exploiting the well-known saddle-point method we determine the number of multisets of total size $n$ with $N$ components, that is, the coefficient of $x^ny^N$ in $G(x,y)$, asymptotically as $n\to\infty$ and for all ranges of $N$. Our results reveal a phase transition in the structure of the counting formula that depends on the ratio $n/N$ and that demonstrates a prototypical passage from a bivariate local limit to an univariate one.

No reviews yet.

No comments yet.