Select Page

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!