go-v.orgdoi

Counting Set Systems by Weight

Martin Klazar · The Electronic Journal of Combinatorics · 2005

  • DOI 10.37236/1908
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2005

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2005

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]$.

Open the resolved locator · 10.37236/1908

Metadata licence: OpenAlex metadata (CC0)