Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-26T21:08:31.133Z Has data issue: false hasContentIssue false

ASYMPTOTIC ENUMERATION AND LOGICAL LIMIT LAWS FOR EXPANSIVE MULTISETS AND SELECTIONS

Published online by Cambridge University Press:  22 February 2006

BORIS L. GRANOVSKY
Affiliation:
Department of Mathematics, Technion-Israel Institute of Technology, Haifa 32000, [email protected]
DUDLEY STARK
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, United [email protected]
Get access

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.

Type
Notes and Papers
Copyright
The London Mathematical Society 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)