Counting Set Systems by Weight

  • Martin Klazar

Abstract

Applying enumeration of sparse set partitions, we show that the number of set systems $H\subset\exp(\{1,2,\dots,n\})$ such that $\emptyset\notin H$, $\sum_{E\in H} |E|=n$ and $\bigcup_{E\in H} E=\{1,2,\dots,m\}$, $m\le n$, 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 the 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 $\sum_{i=1}^k x^i/i!-1$ in $(0,1]$.

Published
2005-02-14
Article Number
R11