Let U = {1,2,…,𝑛}. Let 𝐴={(𝑥, 𝑋)| 𝑥 ∈ 𝑋, 𝑋 ⊆𝑈}. Consider the following two statements on |𝐴|. I. |A|=n 2^{n-1} II |A|=\sum_{k-1}^{n} k(\table n ; k) Which of the above statements is/are TRUE?

Correct Answer is : Both I and II

GATE Computer Science (CS) 2019 Solved Papers

Question : 15 of 65

Marks: +1, -0

Let U = {1,2,…,𝑛}. Let 𝐴={(𝑥, 𝑋)| 𝑥 ∈ 𝑋, 𝑋 ⊆𝑈}. Consider the following two statements on |𝐴|.
I.

|A|=n 2^{n-1}

|A|=∑↙{k-1}↖{n} k(\table n ; k)

Which of the above statements is/are TRUE?

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

Validate

Solution:

A = {(x, X), x ∈ X and X ⊆ U}
The number of k element subsets of a set U with n elements

=(\table n ; k)={ }^{n} C_{k}

The number of possible ordered pairs

( {x},

{X}

) where

{x} ∈ {X}

{k} ⋅{ }^{ {n}} {C}_{ {k}}

for a given value of

{k}

from 1 to

{n}

.
So total number of ordered pairs in A

={|A|}=∑↙{k=1}↖{n} k ⋅{ }^{n} C_{k}=∑↙{k=1}↖{n} k ⋅(\table n ; k )

So II is correct.
(Note that k = 0 is excluded since empty set has no elements and cannot form an order pair such as (x, X)). But since by the combinational identity

∑↙{k=1}↖{n} k ⋅(\table n ; k)=n .2^{n-1}

So I is also correct.
So both I and II are correct.

Go to Question:

Prev Question

Next Question