Asymptotic enumeration and logical limit laws for expansive multisets and selections

Abstract

Given a sequence of integers $a_j,j\ge 1,$ a multiset is a combinatorial object composed of unordered components, such that there are exactly $a_j$ one-component multisets of size $j.$ When $a_j\asymp j^{r-1}{y}^j$ for some $r>0$, $y\ge 1$, then the multiset is called {\em expansive}. Let $c_n$ be the number of multisets of total size $n$. Using a probabilistic approach, we prove for expansive multisets that $c_n/c_{n+1}\to 1$ and that $c_n/c_{n+1}<1$ for large enough $n$. This allows us to prove Monadic Second Order Limit Laws for expansive multisets. The above results are extended to a class of expansive multisets with oscillation. Moreover, under the condition $a_j=K{j}^{r-1}{y}^j+O(y^{\nu j}),$ where $K>0$, $r>0$, $y>1$, $\nu \in (0,1)$, we find an explicit asymptotic formula for $c_n$. In a similar way we study the asymptotic behavior of selections which are defined as multisets composed of components of distinct sizes.

20 pages. This version contains a few minor corrections and changes.It will be published in J. of the London Math. Society