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?
Best Answer
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$.