If we have a Set U such that |U| = n , then we can make subsets from it of size k in C(n,k) ways. In each of those subsets of size k we can select a single element in k ways.
eg; lets say U = {1,2,3} then number of subsets of size 2 will be C(3,2) = 3 i.e {{1,2} , {2,3},{1,3}} and for each of them we can select a single item in 2 ways i.e k ways coz k = 2. Therefore total tuples of the form (x,X) is 3 * 2 i.e 6 . Which are as follows :
(1,{1,2}) , (2,{1,2}) , (2,{2,3}) , (3,{2,3}) , (1,{1,3}) , (3,{1,3})
Note : When we do a subset of set , the empty set i.e phi will also pop but it has no "x" that belongs to it coz it's empty . Hence there can be no tuple (x,X) such that x belongs to X and X is phi or empty.
Therefore , if we do the above process for k = 1 to n the the general formula becomes "sigma (k*C(n,k))" for k = 1 to n .
Option 2 is just the compact version of option 1 [Kindly refer wiki Binomial Coefficient page]
