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.
Find the number of different sets C such that $B\subset C\subset A$
-
0Hint: 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. – 2012-08-12
4 Answers
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.
$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$?
-
0Many Thanks to all – 2012-08-12
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$.
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}$.