2004/04/11 by Martin Klazar, Klazar, Martin
Computer Science · Mathematics · #05A16 #05A18 #Advanced Combinatorial Mathematics #Advanced Database Systems and Queries #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics #math.CO #msc:05A16 #msc:05A18
paper · pdf · doi:10.48550/arxiv.math/0404217
10 pages
arxiv created 2004/04/11 · openalex publication_date 2004/04/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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))nbn where bn 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/alphak+o(1))nbn where alphak is the unique root of xk/k!+...+x1/1!-1 in (0,1].