Counting set systems by weight
The electronic journal of combinatorics, Tome 12 (2005)
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]$.
@article{10_37236_1908,
author = {Martin Klazar},
title = {Counting set systems by weight},
journal = {The electronic journal of combinatorics},
year = {2005},
volume = {12},
doi = {10.37236/1908},
zbl = {1065.05016},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1908/}
}
Martin Klazar. Counting set systems by weight. The electronic journal of combinatorics, Tome 12 (2005). doi: 10.37236/1908
Cité par Sources :