Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Assume that A consists of n elements and $B\subset A$ consists of k elements. Find the number of different sets C such that $B\subset C\subset A$. I am reading the A. Shen and N. K. Vereshchagin book, Basic Set Theory. I try to use Combinatorics for solve the question but still I can not find a solution for the general case. Many Thanks.

share|improve this question
    
Hint: Elements in C must contain elements from set B. So There are only $(n-k)$ options to choose from because the $k$ of them are mandatory. –  FrenzY DT. Aug 12 '12 at 13:48

4 Answers 4

up vote 2 down vote accepted

So one must have $k \leq n$. $A - B$ is a set of $n - k$ elements. If $P \subset A - B$, then $A \subset B \cup P \subset A$. On the other hand if $B \subset C \subset A$, then $P = C - B$ is a subset of $A - B$.

So all such $C$ are in correspondence with subsets of $A - B$. Since $A - B$ is a set of size $n - k$. There are $2^{n -k}$ possibilities for $C$.

share|improve this answer
1  
Not leaving much for OP to do. –  Gerry Myerson Aug 12 '12 at 13:52
1  
@GerryMyerson It is not tagged as homework and did not ask for a hint, so I assumed the person just wanted the answer. –  William Aug 12 '12 at 13:54
    
@William Whether this was tagged as (homework) or not, the problem is: Should one provide a full answer to such a question? What do you think? –  Did Aug 12 '12 at 14:02
2  
@did Personally, I just answer homework questions. People who are morally oppose to it, think the asker did not put enough effort into it, or think they are taking advantage of the commmunity, or whatever other reason, should just refrain from answering. Getting the answer is useful for learning if you take the time to really understand the answer. If there is only value in figuring everything out yourself, you would never accomplish anything. –  William Aug 12 '12 at 14:17
1  
William, you assumed OP just wanted the answer; I assumed OP would enjoy working out the details after being pointed in the right direction. Only OP knows for sure. But if you're right, then OP can always ask for more help, if a hint isn't what OP wants, whereas, if I'm right, then a full answer rather spoils things for OP. So I'll continue to give pointers (mostly), and I'll continue to comment when others don't leave any work for OPs. –  Gerry Myerson Aug 12 '12 at 23:21

$C$ must have all the elements that are in $B$, and none of the elements that aren't in $A$, so the only wiggle room is in the elements that are in $A$ but not in $B$ - each of those elements could either be in $C$, or not be in $C$. So, how many elements are there that are in $A$ but not in $B$? and how many ways to choose the ones to put in $C$?

share|improve this answer
    
Many Thanks to all –  Hernan Aug 12 '12 at 14:04

Choose any subset of the $n-k$ elements that are in A but not in B. The number of possible such subsets is $2^{n-k}$.

share|improve this answer

2^(n-k) - 2. Because C must contain all the k elements. From the other n-k elements, there are 2^(n-k) possible different subsets, but two cases (namely A and B) must be excluded.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.