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!

Combinatorics and sets

  1. Dec 2, 2016 #1
    • Member warned that an attempt must be shown
    1. The problem statement, all variables and given/known data
    1. Given sample space U with n objects. A ⊂ U, and A has k objects. A ∩ B ≠∅
    What are all the possibilities for B?

    2. Relevant equations

    2n - All possibilities for set B with n objects

    3. The attempt at a solution

    I don't know where even to begin... The question itself confuses me.
     
  2. jcsd
  3. Dec 2, 2016 #2

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Hello again,

    Entering a new subject area always takes some getting used to.
    You write 'What are all the possibilities for B?' but I suppose (and hope) you mean 'How many B are possible? '

    In the relevant equation the ∅ is included, right ? But is it a posssibility for B given that A ∩ B ≠∅ ?
    Does the number k have influence on the answer ?
     
  4. Dec 3, 2016 #3
    Yea, it should be "how many", just bad translation on my part. Didn't understand your other 2 questions. What is k in this question?
     
  5. Dec 3, 2016 #4

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    If you are stuck on this sort of problem, you should always try an example. Try ##n =3## and ##k =2##.
     
  6. Dec 3, 2016 #5
    Oh I got confused. I think the answer might be 2n-k ... But if A and B have something in common, subtracting k might subtract some objects that exist in B?
     
  7. Dec 3, 2016 #6

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You can check your formula with the example numbers I suggested.
     
  8. Dec 3, 2016 #7
    21 ? I still don't really get it.
     
  9. Dec 3, 2016 #8

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Why not do the example? It helps to work it out for some specific numbers. You should be able to list all possible sets for B and count them.
     
  10. Dec 3, 2016 #9
    Well ok... U has 3 objects. A has 2. Now, we know that B has something in common with A... But if we don't know the size of B, how can we know if it is equal to A, or maybe smaller?
     
  11. Dec 3, 2016 #10

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I don't think you understand this problem. It's asking you to count how many possibilities you have for B. You can go through all the options for B and count how many meet the requirements.
     
  12. Dec 3, 2016 #11
    Clearly I'm very confused... if n=3 and k=2... Well, I think A could have 4 options... {1,2},{1},{2},{} ...
    Seems to me B could be {1,2,3},{1,2},{1},{2},{3,2},{}.... Which is 2n-2n-k...
     
  13. Dec 3, 2016 #12

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No. ##U## and ##A## are fixed. ##B## is the only "variable" set.
     
  14. Dec 3, 2016 #13
    Hmm I see. So B could have 2 objects in common in A, or 1. It can also have another object... Maybe 2n? After all, B could be equal to A...
     
  15. Dec 3, 2016 #14

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That's all good, apart from another guess at the answer. You still haven't solved the problem for ##n = 3, k = 2##.

    These problems are about finding a process or method for counting. That's why trying some examples is invaluable. It also gives you a test for any general answer you work out.
     
  16. Dec 3, 2016 #15
    Still can't wrap my head around this...umm.. If U has 3 objetcs, and A has two, B must have at least 1 object in common with A... So it can have either 1 or 2 objetcs that are in A, and maybe have another object from U... So... 2x2... =4 = 2k?
     
  17. Dec 3, 2016 #16
    For sure ##2^k## is a lower bound for the possibilities of B, because B can be any subset of A, in which case A∩B=B≠∅. But there are also other possibilities for B.
     
  18. Dec 4, 2016 #17

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You need to write down all the possibilities for B.

    1
    2
    3
    1, 2
    1, 3
    2, 3
    1, 2, 3

    Assuming A is the set 1, 2 how many of the above possibilities for B meet the requirements?
     
  19. Dec 4, 2016 #18
    6... Which is 2n-2n-k
     
  20. Dec 4, 2016 #19

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Is that true in general, then? If so, why?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted