Set cover: To show the number of minimum coverable combination of the power set of universe $U$ is less than $2^n$

Question

Given a set $U=\{1,2,...,n\}$, and its power set $\mathcal S=\{S_1,...,S_{2^n-1}\}$(without emptyset $\emptyset$), a minimum coverable combination is $S_i\cup...\cup S_k=U$ and $S_i,...,S_k$ are pairwise disjoint.

For example, when $U=\{1,2,3\}$, then $\mathcal S=\{\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$ and a minimum coverable combination is $S_4=\{1,2\}$ and $S_3=\{3\}$ then $S_4\cup S_3=U$ and $S_4\cap S_3=\emptyset$.(don't count the permutations so $S_4\cup S_3$ is considered the same as $S_3\cup S_4$)

Now the question is to prove the number of minimum coverable combination of $U$ is less than or equal to $2^n$

Answer 1

Let $U = \{ 1, 2, 3, 4, 5 \}$. Here are some minimum coverable combinations of $U$:

$\begin{align*} 1. \: & \{ 1, 2, 3, 4, 5 \} \\ 2. \: & \{ 1 \}, \{ 2, 3, 4, 5 \} \\ 3. \: & \{ 2 \}, \{ 1, 3, 4, 5 \} \\ 4. \: & \{ 3 \}, \{ 1, 2, 4, 5 \} \\ 5. \: & \{ 4 \}, \{ 1, 2, 3, 5 \} \\ 6. \: & \{ 5 \}, \{ 1, 2, 3, 4 \} \\ 7. \: & \{ 1, 2 \}, \{ 3, 4, 5 \} \\ 8. \: & \{ 1, 3 \}, \{ 2, 4, 5 \} \\ 9. \: & \{ 1, 4 \}, \{ 2, 3, 5 \} \\ 10. \: & \{ 1, 5 \}, \{ 2, 3, 4 \} \\ 11. \: & \{ 2, 3 \}, \{ 1, 4, 5 \} \\ 12. \: & \{ 2, 4 \}, \{ 1, 3, 5 \} \\ 13. \: & \{ 2, 5 \}, \{ 1, 3, 4 \} \\ 14. \: & \{ 3, 4 \}, \{ 1, 2, 5 \} \\ 15. \: & \{ 3, 5 \}, \{ 1, 2, 4 \} \\ 16. \: & \{ 4, 5 \}, \{ 1, 2, 3 \} \\ 17. \: & \{ 1 \}, \{ 2 \}, \{ 3, 4, 5 \} \\ 18. \: & \{ 1 \}, \{ 3 \}, \{ 2, 4, 5 \} \\ 19. \: & \{ 1 \}, \{ 4 \}, \{ 2, 3, 5 \} \\ 20. \: & \{ 1 \}, \{ 5 \}, \{ 2, 3, 4 \} \\ 21. \: & \{ 2 \}, \{ 3 \}, \{ 1, 4, 5 \} \\ 22. \: & \{ 2 \}, \{ 4 \}, \{ 1, 3, 5 \} \\ 23. \: & \{ 2 \}, \{ 5 \}, \{ 1, 3, 4 \} \\ 24. \: & \{ 3 \}, \{ 4 \}, \{ 1, 2, 5 \} \\ 25. \: & \{ 3 \}, \{ 5 \}, \{ 1, 2, 4 \} \\ 26. \: & \{ 4 \}, \{ 5 \}, \{ 1, 2, 3 \} \\ 27. \: & \{ 1 \}, \{ 2, 3 \}, \{ 4, 5 \} \\ 28. \: & \{ 1 \}, \{ 2, 4 \}, \{ 3, 5 \} \\ 29. \: & \{ 1 \}, \{ 2, 5 \}, \{ 3, 4 \} \\ 30. \: & \{ 2 \}, \{ 1, 3 \}, \{ 4, 5 \} \\ 31. \: & \{ 2 \}, \{ 1, 4 \}, \{ 3, 5 \} \\ 32. \: & \{ 2 \}, \{ 1, 5 \}, \{ 3, 4 \} \\ 33. \: & \{ 3 \}, \{ 1, 2 \}, \{ 4, 5 \} \\ 34. \: & \{ 3 \}, \{ 1, 4 \}, \{ 2, 5 \} \\ 35. \: & \{ 3 \}, \{ 1, 5 \}, \{ 2, 4 \} \\ 36. \: & \{ 4 \}, \{ 1, 2 \}, \{ 3, 5 \} \\ 37. \: & \{ 4 \}, \{ 1, 3 \}, \{ 2, 5 \} \\ 38. \: & \{ 4 \}, \{ 1, 5 \}, \{ 2, 3 \} \\ 39. \: & \{ 5 \}, \{ 1, 2 \}, \{ 3, 4 \} \\ 40. \: & \{ 5 \}, \{ 1, 3 \}, \{ 2, 4 \} \\ 41. \: & \{ 5 \}, \{ 1, 4 \}, \{ 2, 3 \} \\ \end{align*}$

There are more than $2^5 = 32$, so the claim is false.

Answer 2

Let $B_n$ denote the number of partitions of the set $[n]:=\{1,2,\ldots,n\}$. This is known as the $n$-th Bell number. The first few values are $B_0=1$, $B_1=1$, $B_2=2$, $B_3=5$, $B_4=15$, and $B_5=52$. It can be shown that $$B_{n+1}=\sum_{k=0}^n\,\binom{n}{k}\,B_k\text{ and }B_n=\sum_{k=0}^n\,\left\{\begin{array}{c}n\\k\end{array}\right\}$$ for all $n\in\mathbb{Z}_{>0}$, where $$\left\{\begin{array}{c}n\\k\end{array}\right\}=\frac{1}{k!}\,\sum_{j=0}^k\,(-1)^{k-j}\,\binom{k}{j}\,j^n$$ is the Stirling number of the second kind.

It is known that $$B_n \approx n^{-\frac{1}{2}}\,\left(\frac{n}{W(n)}\right)^{n+\frac{1}{2}}\,\exp\left(\frac{n}{W(n)}-n-1\right)\,,$$ where $W$ is the Lambert $W$-function. That is, using $W(n)\approx \ln(n)$, we get that $$B_n > \left(\frac{n}{\text{e}\,\ln(n)}\right)^n$$ for every positive integer $n$. Therefore, $B_n$ grows much faster than $2^n$.