Counting Double Subsets | ISI MStat 2014 Sample PSB Problem 3

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!