GATE CS 2021 Set 2 Q.60 (CS Q.50): Combinatorics, Counting, Recurrence Relations and Generating Functions

Let $S$ be a set consisting of 10 elements. The number of tuples of the form $(A, B)$ such that $A$ and $B$ are subsets of $S$ , and $A \subseteq B$ is ______.

Your answer

Official answer and solution

Official answer: 59049
From: Official GATE 2021 answer key

Solution

Consider the membership status of each element of $S$ with respect to the subset pair $(A, B)$ satisfying $A \subseteq B$ .

Let $S = \{x_1, x_2, \dots, x_{10}\}$ be a set of 10 elements.

We need to find the number of ordered pairs of subsets $(A, B)$ such that $A \subseteq B \subseteq S$ .

For any element $x \in S$ , consider its membership in $A$ and $B$ . Since $A \subseteq B$ , if $x \in A$ , then $x$ must also belong to $B$ . The possible disjoint cases for each element $x$ are:

$x \in A$ and $x \in B$
$x \notin A$ and $x \in B$
$x \notin A$ and $x \notin B$

The fourth case ( $x \in A$ and $x \notin B$ ) is impossible because $A \subseteq B$ .

Thus, for each of the 10 elements in $S$ , there are exactly 3 independent choices. By the product rule of counting, the total number of such tuples $(A, B)$ is:

3^{10} = 59049

Final answer

59049

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 60 of 65, printed as CS Q.50
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source