Covering count of a set of $n$ elements

Question

Let $\Omega_n=\{1,2,\cdots,n\}$, $A_1,\cdots,A_r$ is called a covering of $A$, if $\bigcup_{i=1}^r A_i=\Omega_n, \emptyset\neq A_i\subset \Omega_n$, $A_i\neq A_j$, $r=1,2,\cdots$. Denote by $C_n$ the count of different coverings. Then $C_1=1, C_2=5$, what is $C_3$?

Clearly, $C_1=1$. For $\Omega_2$, we have $\Omega_2=\{1\}\cup \{2\}=\{1,2\}=\{1\}\cup\{1,2\}=\{2\}\cup \{1,2\}$. It seems that $C_2=4$?

For $\Omega_3$, we have $\Omega_3=\{1\}\cup\{ 2 \}\cup \{ 3 \} =\{1 \}\cup \{2,3 \} =\{ 2 \}\cup \{ 1,3 \} =\{ 3\}\cup \{ 1,2 \} =\{ 1,2 \}\cup \{ 2,3\} =\{ 1,3 \}\cup \{ 2,3 \} =\{ 1,3 \}\cup \{ 1,2 \} =\{ 1,2,3\} =A\cup \{1,2,3 \}$, where $\emptyset \neq A\subsetneq \Omega_3$. So $C_3=1+6+(2^3-1)=14$. Is this right?

Answer 1

You want to count the number of subsets of $\mathcal P(\Omega_n)\setminus \{\varnothing\}$ whose union is $\Omega_n$. In English, $\{A_1,A_2,\dots,A_r\}$ is a subset of the power set of $\Omega_n$, except the empty set is disallowed.

This is easily accomplished with the principle of inclusion-exclusion. That is, if we ignored the condition that the union had to be all of $\Omega_n$, then the number of subsets of $\mathcal P(\Omega_n)\setminus \{\varnothing\}$ is $2^{2^n-1}$. From these, for each $i\in \Omega_n$, we must subtract the subsets whose union does not contain $i$, so we are subtracting the number of subsets of $\mathcal P(\Omega_n\setminus \{i\})\setminus \{\varnothing\}$. Adding up over all $i\in \Omega_n$, the number of subsets being subtracted is $n\cdot2^{2^{n-1}-1}$. However, you then need to add back in the doubly subtracted sets, then subtract out the triply subtracted sets, and so on. The final answer is $$ \boxed{\sum_{k=0}^n(-1)^k\binom{n}k 2^{(2^{n-k}-1)}} $$ For example, when $n=2$, the number of ways should be $$ 2^{2^2-1}-2\cdot 2^{2^1-1}+2^{2^0-1}=2^3-2\cdot 2^1+2^0=5\;\color{#0d0}{\checkmark} $$ When $n=3$, the result is $$ 2^{2^3-1}-3\cdot 2^{2^2-1}+3\cdot 2^{2^1-1}-2^{2^0-1}=2^7-3\cdot 2^3+3\cdot 2^1-2^0=109 $$ These results are confirmed by https://oeis.org/A003465.

---

As a side note, a pretty commonly accepted notation for $\{1,\dots,n\}$ is $[n]$, which I think is much prettier than $\Omega_n$.

Answer 2

Let $[n] = \{1,2,\dots,n\}$. $|\mathcal P([n])|=2^n$ and $|\mathcal P(\mathcal P([n]))|=2^{2^n}$ so there are $2^{2^n}$ possible families of subsets of $[n]$ to choose from. For the present, we allow $\emptyset$ to be one of the subsets.

Now for each element $x$ of $[n]$ we must exclude the families that don't cover $x$. There are $2^{2^{n-1}}$ of these, so we have $$2^{2^n}-n2^{2^{n-1}}$$ But families that fail to cover two elements have been subtracted twice, so we must add these back in, giving $$2^{2^n}-n2^{2^{n-1}}+\binom n22^{2^{n-2}}$$ Now the families that fail to cover three elements have been added in once, subtracted $3$ times and added back in three times, so they've been counted once. We must subtract them. Continuing in this fashion, by the principle of inclusion and exclusion, we get $$\sum_{k=0}^n(-1)^k\binom nk2^{2^{n-k}}=\sum_{k=0}^n(-1)^{n-k}\binom nk2^{2^k}\tag1 $$ The only problem is that this is the number of covers including covers that contain $\emptyset$. There is a bijection between covers that contain $\emptyset$ and those that don't; simply add $\emptyset$ to a cover not containing $\emptyset$ of remove it from a cover containing $\emptyset$.

That is, we want exactly half the cover counted by $(1)$ and the final result is $$\frac12\sum_{k=0}^n(-1)^{n-k}\binom nk2^{2^k}$$