1
$\begingroup$

A covering of a set $S$ is a set $\{A_1,A_2,\cdots,A_t$} of non-empty subsets of $S$ such that $A_1\cup A_2\cup\cdots\cup A_t$ is $S$. (Note that $A_i\neq A_j$ for $i\neq j$; also $t$ can vary from 1 to $2^{|S|}-1$. The sets are not required to be disjoint). Use the principle of inclusion-exclusion to find the number of coverings of an $n$-set $S$.

I'm a little confused on how to start this problem, and what the ambient set and properties should be. Any hints for those would be appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ So your covering is a subset $F$ of $P\left(S\right)$ (the power set of $S$) which is required to satisfy the condition $A_1 \cup A_2 \cup \cdots \cup A_t = S$. Can you restate the latter condition as "$F$ satisfies neither $P_1$ nor $P_2$ nor ..." for some bunch of properties $P_1, P_2, \ldots$ ? $\endgroup$ Nov 4 '19 at 4:06
0
$\begingroup$

We have $n$ conditions that each of the $n$ elements be covered. There are $\binom nk$ ways to choose $k$ particular conditions, and there are $2^{2^{n-k}-1}$ subsets of the power set that violate these conditions, namely, any set of sets that don't contain any of the $k$ elements. (We need to subtract $1$ because the sets must not be empty.) Thus, by inclusion–exclusion, the number of covers is

$$ \sum_{k=0}^n(-1)^k\binom nk2^{2^{n-k}-1}\;. $$

For $n=0,1,2$ this yields $1,1,5$, and indeed the set $\{1,2\}$ has the $5$ covers $\{\{1,2\}\}, \{\{1\},\{2\}\}$, $\{\{1,2\},\{2\}\}$, $\{\{1\},\{1,2\}\}$ and $\{\{1\},\{2\},\{1,2\}\}$.

This is OEIS sequence A003465.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.