Thread: unlabeled subsets

1. How many unlabeled families of subsets of a $\displaystyle 3 $-set are there?

It is just $\displaystyle 4 $? Because you can have a subset with $\displaystyle 0,1,2 $ or $\displaystyle 3 $ elements?


2. Prove that the number $\displaystyle F(n) $ of unlabeled families of subsets of an $\displaystyle n $-set satisfies $\displaystyle \log_{2} F(n) = 2^n +O(n \log n) $.

So $\displaystyle F(n) = n+1 $. Thus we want to show that $\displaystyle 2^{2^{n}+O(n \log n)} = n+1 $. Now $\displaystyle O(n \log n) $ means that there is a function $\displaystyle g(n) $ such that $\displaystyle |g(n)| < c(n \log n) $ for some constant $\displaystyle c $. Maybe we can rewrite the LHS as $\displaystyle 2^{2^n} \cdot 2^{O(n \log n)} $?

actually these are families of subsets, so my answer is probably not correct.

I know that there are $\displaystyle 2^{2^3} $ labeled subsets. The power set $\displaystyle |\mathcal{P}(S)| = 2^n $ for example. Isn't this what is meant by families of subsets?