Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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 Li Aug 12 '12 at 13:48
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|cite|improve this answer

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