Counting set systems by weight

Original · EN

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))ⁿbₙ where bₙ 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ₖ+o(1))ⁿbₙ where alphaₖ is the unique root of xᵏ/k!+...+x¹/1!-1 in (0,1].