Results 1 to 5 of 5

Math Help - Subsets

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Subsets

    We want to select two subsets A and B of [n] so that A \cap B \neq\emptyset. In how many different ways can we do this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Re: Subsets

    First we find how many ways are there to choose two subsets A and B of [n] without worrying about what their intersection is.

    There are 2^{2n} ways of doing this.
    Then we deduct the number of cases when A \cap B=\Phi. That is tiresome.

    Another way would be to make a series:
    Case 1: there is one element in common between A and B.
    Case2: There are two elements in common between A and B.
    .
    .
    .
    and so on.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: Subsets

    I'm going to assume that we consider
    A={1}, B={1,2}
    and
    A={1,2}, B={1}
    to be distinct cases.

    How many ways are there to select two subsets without any restriction? Each element of {1, 2, ..., n} can be in
    (1) neither A nor B,
    (2) in A only,
    (3) in B only, or
    (4) in both A and B.
    So there are 4^n ways to select A and B.

    How many ways are there if A and B must be disjoint? We simply eliminate case (4) above. So there are 3^n ways to select A and B if they must be disjoint.

    So the number of ways to select A and B if they must not be disjoint is 4^n - 3^n.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162

    Re: Subsets

    Quote Originally Posted by awkward View Post
    I'm going to assume that we consider
    A={1}, B={1,2}
    and
    A={1,2}, B={1}
    to be distinct cases.

    How many ways are there to select two subsets without any restriction? Each element of {1, 2, ..., n} can be in
    (1) neither A nor B,
    (2) in A only,
    (3) in B only, or
    (4) in both A and B.
    So there are 4^n ways to select A and B.

    How many ways are there if A and B must be disjoint? We simply eliminate case (4) above. So there are 3^n ways to select A and B if they must be disjoint.

    So the number of ways to select A and B if they must not be disjoint is 4^n - 3^n.
    Since the OP talks of selecting two subsets, A={1,2}, B={1} and A={1}, B={1,2} should be the same case. A slight modification of your formula takes care of that.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: Subsets

    Quote Originally Posted by Traveller View Post
    Since the OP talks of selecting two subsets, A={1,2}, B={1} and A={1}, B={1,2} should be the same case. A slight modification of your formula takes care of that.
    You may be right in your interpretation, but the OP talks of "selecting two subsets A and B"-- so it's really not clear, at least not to me.
    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, 02:26 AM
  2. Subsets
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: December 29th 2010, 11:33 AM
  3. How many subsets
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 17th 2010, 06:41 AM
  4. Subsets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 1st 2009, 08:54 PM
  5. Subsets
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: October 22nd 2008, 01:58 AM

Search Tags


/mathhelpforum @mathhelpforum