Skip Navigation

Journal of the London Mathematical Society 2006 73(1):252-272; doi:10.1112/S0024610705022477
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Granovsky, B. L.
Right arrow Articles by Stark, D.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The London Mathematical Society

Asymptotic Enumeration and Logical Limit Laws for Expansive Multisets and Selections

Boris L. Granovsky and Dudley Stark

Department of Mathematics, Technion-Israel Institute of Technology Haifa 32000, Israel mar18aa{at}techunix.technion.ac.i
School of Mathematical Sciences, Queen Mary, University of London London E1 4NS, United Kingdom D.S.Stark{at}maths.qmul.ac.uk

Received 16 July 2004. Revision received 25 February 2005.

Given a sequence of integers aj, j ≥ 1, a multiset is a combinatorial object composed of unordered components, such that there are exactly aj one-component multisets of size j. When aj {asymp} jr–1 yj for some r > 0, y ≥ 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 cn/cn+1 -> 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 aj = Kjr–1 yj + O(y{nu} j), where K > 0, r > 0, y > 1, {nu} isin (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.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.