Let $U = \{1,2, \dots, n\}$. Let $A = \{(x, X)|x \in X, X \subseteq U\}$. Consider the following two statements on $|A|$. I. $|A| = n2^{n-1}$ II. $|A| = \sum_{k=1}^n k \binom{n}{k}$ Which of the above statements is/are TRUE?

We need to find the cardinality of the set $A = \{(x, X) \mid x \in X, X \subseteq U\}$.

• Method 1 (Counting by element $x$): There are $n$ possible choices for the element $x \in U$. For each fixed $x$, the set $X$ must contain $x$, and the remaining $n-1$ elements of $U$ can be either included or excluded. This gives $2^{n-1}$ valid subsets $X$ for each $x$.

  $$|A| = n \times 2^{n-1}$$

  Thus, Statement I is TRUE.

• Method 2 (Counting by size of subset $|X| = k$): For a fixed subset size $k$ (where $1 \le k \le n$), there are $\binom{n}{k}$ ways to choose $X \subseteq U$. For each such subset $X$, there are $k$ choices for $x \in X$. Summing over all possible subset sizes from $k = 1$ to $n$:

  $$|A| = \sum_{k=1}^n k \binom{n}{k}$$

  Thus, Statement II is TRUE.

Using the identity $k\binom{n}{k} = n\binom{n-1}{k-1}$, we also have:

Both statements are correct, so option (C) is the correct choice.