Counting set systems by weight

MaRDI QIDQ1773202zbMATH OpenFDO

Authors Martin Klazar

Publication date 25 April 2005

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0404217, https://eudml.org/doc/124752, http://www.emis.de/journals/EJC/Volume_12/Abstracts/v12i1r11.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Bell numbersset partitions

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Partitions of sets (05A18)

Abstract: Applying the enumeration of sparse set partitions, we show that the number of set systems H such that the emptyset is not in H, the total cardinality of edges in H is n, and the vertex set of H is {1, 2, ..., m}, equals (1/log(2)+o(1))^nb_n where b_n is the n-th Bell number. The same asymptotics holds if H may be a multiset. If vertex degrees in H are restricted to be at most k, the asymptotics is (1/alpha_k+o(1))^nb_n where alpha_k is the unique root of x^k/k!+...+x^1/1!-1 in (0,1].

Review text

It is well known that the Bell numbers count the total number of ways a set of \(n\) elements can be partitioned into nonempty, mutually disjoint subsets. This paper considers the situation when the subsets may intersect. The main result states that such a number is asymptotically larger than the Bell number by an exponential factor. The enumeration problem can also be formulated as counting 0-1 matrices satisfying certain properties.

Recommendations

• Sum of weighted records in set partitions
• scientific article; zbMATH DE number 5693587
• On cross-intersecting families of set partitions
• The asymptotic number of set partitions with unequal block sizes
• The number of unrelated partitions

Cited in

(4)

• Sum of weighted records in set partitions
• Patterns in treeshelves
• Gray codes and lexicographical combinatorial generation for nonnesting and sparse nonnesting set partitions
• Meet and join within the lattice of set partitions

This page was built for publication: Counting set systems by weight

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1773202)