1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The number of subset pairs

  1. Oct 20, 2016 #1
    Mod note: Moved from a technical math forum, so missing the homework template.
    Given a set A = {a1, a2, ..., an} and its two subsets - X, Y so that these subsets satisfy a condition, find the number of such possible (X, Y) pairs

    Condition 1: X ∩ Y = {a1, a2},
    Condition 2: X ⊆ Y,
    Condition 3: | (X - Y) ∪ (Y - X) | = 1

    I've tried to solve these but I still can't figure out the right way to think when solving these.

    For X ∩ Y = the number of subsets is ΣC(n,k) × 2n-k, where k=0÷n.

    This is how I think - so, for Condition 1, X and Y should have only a1 and a2 in common and can have other distinct elements, so we need to choose those two elements but how to choose them for both X and Y?

    For Condition 2, |X| can be k, |Y| can be k (or k-1?), therefore the number of subsets - C(n,k) × C(n,k) = (C(n,k))2? Is this right?

    For Condition 3, X is a subset of Y, or Y is a subset of X, and they have one element in common, right? If so, how to count the number of subsets?
     
    Last edited by a moderator: Oct 20, 2016
  2. jcsd
  3. Oct 20, 2016 #2

    Mark44

    Staff: Mentor

    But Condition 1 says that X ∩ Y is not empty.
    a1 and a2 have to be elements of both X and Y.
    No, |Y| can't be k - 1.
    If |Y| = k, then |X| can be at most k, but at least 2.
    Condition 2 says that X is either a proper subset of Y or X = Y.
    No, they have two elements in common, which is what Condition 1 says.
    If X ⊂ Y, then X - Y = ∅, and Y - X would be all of the elements in Y that aren't elements of X
    If X = Y, then X - Y = Y - X.
     
  4. Oct 20, 2016 #3
    Empty intersection wasn't a part of the problem, I just wrote that to show how I choose X and Y for a given condition (in that case - ∅)

    For Condition 1, if I choose k elements for X (k≥2), then for Y I'll have to choose from n-k elements, that'll be ΣC(n,k) × 2n-k, k=2÷n. How do I say that a1 and a2 and mutual for both X and Y?

    For Condition 2, I just noticed I made a mistake, I should've said |X| is maybe k-1? So if it's a subset of Y then for Y we can choose C(n,k) and for X: 2k

    And for Condition 3, either X-Y or Y-X is ∅, that crossed my mind but I don't get why they have 2 elements in common? Condition 1 is a separate condition.
     
  5. Oct 20, 2016 #4

    fresh_42

    Staff: Mentor

    Does this mean, it consists of three separate exercises instead of all conditions have to hold simultaneously?
    That makes a big difference which you haven't mentioned!
     
  6. Oct 20, 2016 #5
    All of the three are separate conditions, I'm sorry not to have mentioned it before
     
  7. Oct 20, 2016 #6

    Mark44

    Staff: Mentor

    @Lilia, in the future, please post homework-type questions in the Homework & Coursework sections, not in the technical math sections. I have moved your post.
     
  8. Oct 20, 2016 #7

    Mark44

    Staff: Mentor

    For Condition 1, I would investigate the problem with specific numbers for the number of elements in A, such as n = 2, n = 3, n = 4, and look for a pattern.
     
  9. Oct 20, 2016 #8
    Okay, got it.

    For Condition 1, I got ΣC(n,k+2) × 2n-k. Do I also need multiply this by C(n,2) and will that be correct?
     
  10. Oct 21, 2016 #9

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    If ##X \subset Y##, do we not have ##X \cap Y = X##?
     
  11. Oct 21, 2016 #10
    The three conditions are separate conditions, it's X ⊆ Y, so |X| can be anything from 0 to n (for n elements), and |Y| can be at most k, so I wrote ΣC(n,k) × 2n but does this ensure that the chosen Y subset contains X?

    And for Condition 1 I should've written ΣC(n,k+2) × 2n-k-2, where k=0,n-2. Or C(n,2) × (∑C(n-2,k) × 2n-2-k), k=0,n-2?
     
    Last edited: Oct 21, 2016
  12. Oct 22, 2016 #11

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Setting aside the two elements we know both must have, what conditions apply to the rest of X and Y?
    No, X is a subset of Y, Y cannot be smaller. If |X|=k, how many ways are there of choosing Y?
    The first statement is right, but it is not that they have one element in common. Can you draw a Venn diagram?
     
  13. Oct 23, 2016 #12
    Assuming that X-Y is empty, then drawing the Venn diagram - Y is a set (a circle) and X is another set (a circle) fully inside it.

    And, then how many elements do they have in common?
     
  14. Oct 23, 2016 #13

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    That's not the first question to ask here. How many elements do they have NOT in common?
     
    Last edited: Oct 23, 2016
  15. Oct 23, 2016 #14
    That will be A-Y elements
     
  16. Oct 23, 2016 #15

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    This is for condition 3, right? Maybe I need to be clearer. How many elements are in only one of X and Y?
     
  17. Oct 23, 2016 #16
    Yes it's for the 3rd condition.
    If there are k elements in Y (k=0,n) and if X-Y is empty and Y-X isn't empty then Y has more elements than X so there are m=0,k-1 (or m=k-1?) elements in X?
     
  18. Oct 23, 2016 #17

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    That is the interesting question. What do you think?
    (If you are considering the case where X is the smaller, it might be simpler to work in terms of what is the size of Y given the size of X.)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: The number of subset pairs
  1. Subset Question (Replies: 3)

Loading...