Combinatorics and sets

  • Thread starter agargento
  • Start date
  • #1
39
2
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.
 

Answers and Replies

  • #2
BvU
Science Advisor
Homework Helper
14,406
3,719
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
39
2
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?
 
  • #4
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
17,164
8,964
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##.
 
  • #5
39
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?
 
  • #6
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
17,164
8,964
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.
 
  • #7
39
2
You can check your formula with the example numbers I suggested.

21 ? I still don't really get it.
 
  • #8
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
17,164
8,964
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.
 
  • #9
39
2
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?
 
  • #10
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
17,164
8,964
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.
 
  • #11
39
2
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...
 
  • #12
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
17,164
8,964
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.
 
  • #13
39
2
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...
 
  • #14
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
17,164
8,964
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.
 
  • #15
39
2
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?
 
  • #16
Delta2
Homework Helper
Insights Author
Gold Member
3,999
1,571
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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
17,164
8,964
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?
 
  • #18
39
2
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
 
  • #19
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
17,164
8,964
6... Which is 2n-2n-k
Is that true in general, then? If so, why?
 

Related Threads on Combinatorics and sets

  • Last Post
Replies
8
Views
698
Replies
1
Views
2K
Replies
3
Views
964
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
4
Views
2K
Replies
7
Views
693
M
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
578
Replies
1
Views
2K
Top