Results 1 to 3 of 3

Thread: unlabeled subsets

  1. #1
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301

    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)} $?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    actually these are families of subsets, so my answer is probably not correct.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Subsets of R^3
    Posted in the Advanced Algebra Forum
    Replies: 11
    Last Post: May 14th 2011, 01:26 AM
  2. Subsets
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Dec 29th 2010, 10:33 AM
  3. subsets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 1st 2010, 09:52 AM
  4. Labeled and unlabeled
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Feb 25th 2009, 05:55 AM
  5. Subsets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Apr 15th 2008, 01:49 PM

Search Tags


/mathhelpforum @mathhelpforum