Expansive Multisets: Asymptotic Enumeration

Abstract

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\ge 1}(1-x^{k}y{)}^{-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^n{y}^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.