INTRODUCING 5 - days-a-week problem solving session for Math Olympiad and ISI Entrance. Learn More

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\) ?

- Generalization of the idea of counting the total number of subsets of a set.

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}.

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!

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.

JOIN TRIAL
Google