Consider a non-negative sequence $c_n = h(n) \cdot n^{ \alpha-1} \cdot \rho^{ -n}$, where $h$ is slowly varying, $\alpha>0$, $0<\rho<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.

Categories: math.PR math.CO

Expansive Multisets: Asymptotic Enumeration