GATE CS 2021 Set 2 Q50 — Combinatorics: Counting, Recurrence Relations, Generating Functions

We are given a set $S$ with $|S| = 10$. We need to find the number of ordered pairs $(A, B)$ of subsets of $S$ such that $A \subseteq B$.

For any element $x \in S$, there are three mutually exclusive possibilities regarding its membership in the subsets $A$ and $B$:

1. $x \in A$ and $x \in B$
2. $x \notin A$ and $x \in B$
3. $x \notin A$ and $x \notin B$

Note that the case $x \in A$ and $x \notin B$ is impossible because $A \subseteq B$.

Since the choice for each of the $10$ elements in $S$ is independent, the total number of such pairs $(A, B)$ is:

Calculating the value:

Thus, the number of such tuples is 59049.