# Combinatorics and sets

Member warned that an attempt must be shown

## Homework Statement

1. Given sample space U with n objects. A ⊂ U, and A has k objects. A ∩ B ≠∅
What are all the possibilities for B?

## Homework Equations

2n - All possibilities for set B with n objects

## The Attempt at a Solution

I don't know where even to begin... The question itself confuses me.

BvU
Homework Helper
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 ?

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 ?

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?

PeroK
Homework Helper
Gold Member
2020 Award
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?
If you are stuck on this sort of problem, you should always try an example. Try ##n =3## and ##k =2##.

If you are stuck on this sort of problem, you should always try an example. Try ##n =3## and ##k =2##.
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?

PeroK
Homework Helper
Gold Member
2020 Award
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?
You can check your formula with the example numbers I suggested.

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

21 ? I still don't really get it.

PeroK
Homework Helper
Gold Member
2020 Award
21 ? I still don't really get it.
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.

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.

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?

PeroK
Homework Helper
Gold Member
2020 Award
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?
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.

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.

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

PeroK
Homework Helper
Gold Member
2020 Award
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},{3,2}.... Which is 2n-2n-k...
No. ##U## and ##A## are fixed. ##B## is the only "variable" set.

No. ##U## and ##A## are fixed. ##B## is the only "variable" set.
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...

PeroK
Homework Helper
Gold Member
2020 Award
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...
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.

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

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?

Delta2
Homework Helper
Gold Member
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.

PeroK
Homework Helper
Gold Member
2020 Award
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?

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?

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?

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

PeroK