Let U=\1,2,,n\. Let A=\(x,X) x X,\ X U\. Consider the following two statements on A . I. A =n2n-1 II. A = k=1nk nk Which of the above statements is/are TRUE?

GATE 2019 CS – Question 15

Engineering Mathematics · Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) · 1 mark · Multiple choice

Let $U=\{1,2,\dots,n\}$. Let $A=\{(x,X)\mid 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 nk$

Which of the above statements is/are TRUE?

Only I
Only II
Both I and II
Neither I nor II

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) Both I and II

Explanation

Counting pairs by the element $x$: each of the $n$ elements lies in $2^{n-1}$ subsets, so $|A|=n2^{n-1}$. Counting by the size $k$ of $X$, there are $\binom nk$ subsets, each with $k$ choices for $x$, which gives $\sum k\binom nk$. Both are true (and equal).