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!

Related

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!

Related

Leave a ReplyCancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Knowledge Partner

Cheenta is a knowledge partner of Aditya Birla Education Academy

Cheenta Academy

Aditya Birla Education Academy

Cheenta. Passion for Mathematics

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

HALL OF FAME BLOG OFFLINE CLASS

CHEENTA ON DEMAND BOSE OLYMPIAD

Cheenta Academy Private Limited |

support@cheenta.com

Menu