Possibilities for Set B with n Objects in Sample Space U

In summary: Which is 2n-2n-kIs that true in general, then? If so, why?In summary, the number of possibilities for set B, given a sample space U with n objects and subset A with k objects, where A∩B ≠∅, can be calculated by the formula 2n-2n-k. This formula works because for any given value of n and k, the number of possibilities for B will be equal to the number of subsets of A, which is 2k, subtracted from the total number of subsets of U, which is 2n. This accounts for all possible combinations of objects in B while ensuring that A∩B ≠∅.
  • #1
agargento
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.
 
Physics news on Phys.org
  • #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 ?
 
  • #3
BvU said:
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
agargento said:
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
PeroK said:
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
agargento said:
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
PeroK said:
You can check your formula with the example numbers I suggested.

21 ? I still don't really get it.
 
  • #8
agargento said:
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
PeroK said:
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
agargento said:
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
PeroK said:
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
agargento said:
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
PeroK said:
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
agargento said:
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.
 
  • Like
Likes BvU
  • #15
PeroK said:
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
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
agargento said:
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
PeroK said:
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
agargento said:
6... Which is 2n-2n-k
Is that true in general, then? If so, why?
 

1. What is combinatorics?

Combinatorics is a branch of mathematics that deals with the study of counting, arrangement, and selection of objects or elements in a specific way.

2. What are the basic principles of combinatorics?

The basic principles of combinatorics include the fundamental counting principle, permutations, combinations, and the pigeonhole principle.

3. What is the difference between permutations and combinations?

Permutations refer to the arrangement of objects in a specific order, while combinations refer to the selection of objects without considering their order.

4. How is combinatorics applied in real-life scenarios?

Combinatorics is widely used in various fields such as computer science, economics, engineering, and statistics. It is used to solve problems involving probability, optimization, and data analysis.

5. What is the role of sets in combinatorics?

Sets play a crucial role in combinatorics as they provide a way to organize and categorize objects, making it easier to apply combinatorial principles and solve problems.

Similar threads

  • Calculus and Beyond Homework Help
Replies
4
Views
937
  • Calculus and Beyond Homework Help
Replies
0
Views
408
  • Calculus and Beyond Homework Help
Replies
3
Views
482
  • Calculus and Beyond Homework Help
Replies
12
Views
2K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
81
  • Calculus and Beyond Homework Help
Replies
5
Views
748
  • Calculus and Beyond Homework Help
Replies
3
Views
949
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
Back
Top