# 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?