Combinatorics and sets

1. Dec 2, 2016

agargento

• 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. Dec 2, 2016

BvU

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 ?

3. Dec 3, 2016

agargento

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?

4. Dec 3, 2016

PeroK

If you are stuck on this sort of problem, you should always try an example. Try $n =3$ and $k =2$.

5. Dec 3, 2016

agargento

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?

6. Dec 3, 2016

PeroK

You can check your formula with the example numbers I suggested.

7. Dec 3, 2016

agargento

21 ? I still don't really get it.

8. Dec 3, 2016

PeroK

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.

9. Dec 3, 2016

agargento

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?

10. Dec 3, 2016

PeroK

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.

11. Dec 3, 2016

agargento

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...

12. Dec 3, 2016

PeroK

No. $U$ and $A$ are fixed. $B$ is the only "variable" set.

13. Dec 3, 2016

agargento

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...

14. Dec 3, 2016

PeroK

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.

15. Dec 3, 2016

agargento

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?

16. Dec 3, 2016

Delta²

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.

17. Dec 4, 2016

PeroK

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?

18. Dec 4, 2016

agargento

6... Which is 2n-2n-k

19. Dec 4, 2016

PeroK

Is that true in general, then? If so, why?