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.
Problem
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\) ?
Prerequisites
- Generalization of the idea of counting the total number of subsets of a set.
Solution
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
- \(b\) if that element is in \(B \subseteq A\).
- \(a\) if that element is extra in \(A\) and not in \(B\).
- \(0\) if that element is not included in \(A\) hence not in \(B\).
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}.
(a)
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\)
(b)
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\)
Other Methods
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!