unlabeled subsets

**Sampras** · May 30th 2009, 09:28 AM

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

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

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

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

**Sampras** · May 30th 2009, 09:44 AM

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

**Sampras** · May 30th 2009, 03:39 PM

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

Thread: unlabeled subsets

LinkBack

Thread Tools

Display

unlabeled subsets

Similar Math Help Forum Discussions

Subsets of R^3

Subsets

subsets

Labeled and unlabeled

Subsets

Search Tags