Article contents
ASYMPTOTIC ENUMERATION AND LOGICAL LIMIT LAWS FOR EXPANSIVE MULTISETS AND SELECTIONS
Published online by Cambridge University Press: 22 February 2006
Abstract
Given a sequence of integers aj, $j\ge 1$, a multiset is a combinatorial object composed of unordered components, such that there are exactly aj one-component multisets of size j. When $a_j\asymp j^{r-1} y^j$ for some r > 0, $y\geq 1$, then the multiset is called expansive. Let cn 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 cn/cn+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=Kj^{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 cn. In a similar way we study the asymptotic behavior of selections, which are defined as combinatorial objects composed of unordered components of distinct sizes.
Keywords
- Type
- Notes and Papers
- Information
- Copyright
- The London Mathematical Society 2006
- 8
- Cited by