Premium
Asymptotic Enumeration and Logical Limit Laws for Expansive Multisets and Selections
Author(s) -
Granovsky Boris L.,
Stark Dudley
Publication year - 2006
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/s0024610705022477
Subject(s) - multiset , expansive , limit (mathematics) , mathematics , combinatorics , enumeration , sequence (biology) , order (exchange) , class (philosophy) , discrete mathematics , computer science , physics , mathematical analysis , compressive strength , genetics , finance , biology , economics , thermodynamics , artificial intelligence
Given a sequence of integers a j , j ⩾ 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 ≍ j r −1 y j for some r > 0, y ⩾ 1, then the multiset is called 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 → 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 = Kj r −1 y j + O ( y ν j ), where K > 0, r > 0, y > 1, ν ∈ (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 combinatorial objects composed of unordered components of distinct sizes.