This problem is an extension of the bijection principle idea used in counting the number of subsets of a set. This is ISI MStat 2014 Sample Paper PSB Problem 3.
Let \( S = \{1,2, \ldots, n\} \)
(a) In how many ways can we choose two subsets \(A\) and \(B\) of \(S\) so that \(B \neq \emptyset\) and \(B \subseteq A \subseteq S\) ?
(b) In how many of these cases is \(B\) a proper subset of \(A\) ?
It is the same idea as counting the total number of subsets of a set. We used coding schemes.
Coding Scheme
We need three parameters to take note
Example
For \( S = \{1,2, 3, 4, 5, 6\} \).
The coding scheme \( (1, 2, 3, 4, 5, 6) = (a, b, 0, 0, a, a) \) means
\( B = \{ 2 \}, A = \{ 1, 2, 5, 6\}\).
The total number of ssuch strings without any restrictions on number of \(b\) or \(a\) = \(3^n\) since, for each of the \(n\) elements of \(S\), there are three options {\(a, b\), 0}.
The total number of cases with \(B = \emptyset\) = The total number of cases with zero \(b\) = \(2^n\), since for each of the \(n\) elements of \(S\), there are two options {\(a\), 0}.
The total number of cases \(B\) is not a proper subset of \(A\) = The total number of cases {\( A = B\)} = The total number of cases with zero \(a\) = \(2^n\), since for each of the \(n\) elements of \(S\), there are two options {\(b\), 0}.
We need to count how many such strings are there using atleast one \(b\).
The total number of strings using atleast one \(b\) =
the total number of cases without any restrictions - the total number of cases with zero \(b\).
= \(3^n - 2^n\)
We need to count how many such strings are there using atleast one \(a\) and one \(b\).
The total number of strings using atleast one \(a\) and one \(b\) =
The total number of strings using atleast one \(b\) - The total number of strings using atleast one \(b\) and zero \(a\)
= The total number of strings using atleast one \(b\) - The total number of strings using atleast one \(b\) out of {\(b, 0\)}
= \(3^n - 2^n\) - \( 2^n - 1\) = \(3^n - 2^{n+1} +1\)
You can also do it by using methods of Conditional Expectation and Smoothing method, taking a uniform distribution over \(S\). If you have done it in that way, let us know, we will add the solution to the post.
Stay Tuned! Stay Blessed!
This problem is an extension of the bijection principle idea used in counting the number of subsets of a set. This is ISI MStat 2014 Sample Paper PSB Problem 3.
Let \( S = \{1,2, \ldots, n\} \)
(a) In how many ways can we choose two subsets \(A\) and \(B\) of \(S\) so that \(B \neq \emptyset\) and \(B \subseteq A \subseteq S\) ?
(b) In how many of these cases is \(B\) a proper subset of \(A\) ?
It is the same idea as counting the total number of subsets of a set. We used coding schemes.
Coding Scheme
We need three parameters to take note
Example
For \( S = \{1,2, 3, 4, 5, 6\} \).
The coding scheme \( (1, 2, 3, 4, 5, 6) = (a, b, 0, 0, a, a) \) means
\( B = \{ 2 \}, A = \{ 1, 2, 5, 6\}\).
The total number of ssuch strings without any restrictions on number of \(b\) or \(a\) = \(3^n\) since, for each of the \(n\) elements of \(S\), there are three options {\(a, b\), 0}.
The total number of cases with \(B = \emptyset\) = The total number of cases with zero \(b\) = \(2^n\), since for each of the \(n\) elements of \(S\), there are two options {\(a\), 0}.
The total number of cases \(B\) is not a proper subset of \(A\) = The total number of cases {\( A = B\)} = The total number of cases with zero \(a\) = \(2^n\), since for each of the \(n\) elements of \(S\), there are two options {\(b\), 0}.
We need to count how many such strings are there using atleast one \(b\).
The total number of strings using atleast one \(b\) =
the total number of cases without any restrictions - the total number of cases with zero \(b\).
= \(3^n - 2^n\)
We need to count how many such strings are there using atleast one \(a\) and one \(b\).
The total number of strings using atleast one \(a\) and one \(b\) =
The total number of strings using atleast one \(b\) - The total number of strings using atleast one \(b\) and zero \(a\)
= The total number of strings using atleast one \(b\) - The total number of strings using atleast one \(b\) out of {\(b, 0\)}
= \(3^n - 2^n\) - \( 2^n - 1\) = \(3^n - 2^{n+1} +1\)
You can also do it by using methods of Conditional Expectation and Smoothing method, taking a uniform distribution over \(S\). If you have done it in that way, let us know, we will add the solution to the post.
Stay Tuned! Stay Blessed!
