Let U = {1,2,...,n}. Let A = {(x,X)|x ∈ X, X ⊆ U}. Consider the following two statements on |A|.
I. |A| = n2^(n−1)
II. |A| = ∑(k=1 to n) k C(n,k)
Which of the above statements is/are TRUE?

Question

Accepted Answer

Both I and II. Both statements are true because they represent different ways to count the number of pairs (x, X) where x is an element of the subset X of U. The first statement counts all possible subsets and their elements, while the second uses combinatorial counting to arrive at the same total.

Let U = {1,2,...,n}. Let A = {(x,X)|x ∈ X, X ⊆ U}. Consider the following two statements on |A|. I. |A| = n2^(n−1) II. |A| = ∑(k=1 to n) k C(n,k) Which of the above statements is/are TRUE?

Solution

Related GATE Technical questions