GATE CS 2019 Q5 — Combinatorics: Counting, Recurrence Relations, Generating Functions

We are given the set $U = \{1, 2, \dots , n\}$ and the set of pairs:

$$A = \{(x, X) \mid x \in X, X \subseteq U\}$$

We can find the cardinality $|A|$ using two different combinatorial counting methods.

Method 1: Counting by choosing the element $x$ first (Proof of Statement I)

1. There are $n$ choices for the element $x \in U$.
2. For any fixed element $x$, the subset $X$ must contain $x$. The remaining $n-1$ elements of $U$ can either be included in $X$ or excluded. Thus, there are $2^{n-1}$ possible choices for the subset $X$.
3. By the product rule, the total number of valid pairs $(x, X)$ is:$$|A| = n \cdot 2^{n-1}$$

Therefore, Statement I is TRUE.

Method 2: Counting by choosing the subset $X$ first (Proof of Statement II)

1. Let $k$ be the size of the subset $X$, where $1 \le k \le n$ (since $X$ contains at least $x$, $X$ cannot be empty).
2. The number of ways to choose a subset $X \subseteq U$ of size $k$ is $\binom{n}{k}$.
3. Once $X$ of size $k$ is chosen, there are exactly $k$ choices for the element $x \in X$.
4. Summing over all possible subset sizes $k$ from $1$ to $n$, we get:$$|A| = \sum_{k=1}^{n} k \binom{n}{k}$$

Therefore, Statement II is TRUE.

Since both Statement I and Statement II correctly express the cardinality $|A|$, both statements are true.