edited by
11,328 views
28 votes
28 votes

Let $U = \{1, 2, \dots , n\}$ Let $A=\{(x, X) \mid  x \in X, X \subseteq U \}$. Consider the following two statements on $\mid A \mid$.

  1. $\mid A \mid = n2^{n-1}$
  2. $\mid A \mid = \Sigma_{k=1}^{n} k \begin{pmatrix} n \\ k \end{pmatrix}$

Which of the above statements is/are TRUE?

  1. Only I
  2. Only II
  3. Both I and II
  4. Neither I nor II
edited by

4 Answers

Best answer
41 votes
41 votes

Option C: Both are correct.

$\displaystyle | \{X \mid X \subset U\}  | = \begin{pmatrix} n \\ 0 \end{pmatrix} + \begin{pmatrix} n \\ 1 \end{pmatrix} + \begin{pmatrix} n \\ 2 \end{pmatrix} + \cdots + \begin{pmatrix} n \\ n \end{pmatrix} = 2^n$

Now $x$ can be any element of the individual subset $X$.

So $\mid A \mid  = \begin{pmatrix} n \\ 0 \end{pmatrix}  \times 0 + \begin{pmatrix} n \\ 1 \end{pmatrix} \times 1 + \begin{pmatrix} n \\ 2 \end{pmatrix} \times 2 + \cdots + \begin{pmatrix} n \\ n \end{pmatrix} \times n = n \cdot 2^{n-1}$

Note here that for the case when our chosen subset is empty $(X = \emptyset)$, we don't have any member $x \in X$, and hence the term $\begin{pmatrix} n \\ 0 \end{pmatrix} \times 0$ is correct.


Proof that $\bf{\sum_{k=1}^n k \times \begin{pmatrix} n \\ k \end{pmatrix} = n \cdot 2^{n-1}}$

We have the Binomial Expansion:

$(1+x)^n = \begin{pmatrix} n \\ 0 \end{pmatrix} x^0 + \begin{pmatrix} n \\ 1 \end{pmatrix} x^1 + \begin{pmatrix} n \\ 2 \end{pmatrix} x^2 + \cdots + \begin{pmatrix} n \\ n \end{pmatrix} x^n$

Differentiating both sides w.r.t $x$, we get,

$n (1+x)^{n-1} = \begin{pmatrix} n \\ 1 \end{pmatrix} + 2 \times \begin{pmatrix} n \\ 2 \end{pmatrix} x + \cdots + n \times \begin{pmatrix} n \\ n \end{pmatrix} x^{n-1}$

Put $x = 1$ to get

$n \times 2^{n-1} = \begin{pmatrix} n \\ 1 \end{pmatrix} + 2 \times \begin{pmatrix} n \\ 2 \end{pmatrix} + \cdots + n \times \begin{pmatrix} n \\ n \end{pmatrix}$

Q.E.D.

selected by
49 votes
49 votes

APPROACH 1: Trial and Error

 

$\rightarrow$ For $n=2$, $U={1,2}$.

$\rightarrow$ The subsets of  $U$ are $\left \{ \Phi , \{1\},\{2 \}, \{1,2 \} \}\right.$

$\rightarrow$ So,set $X$ has $4$ possibilities as above.

$\rightarrow$ Seeing $x$ as element of $X$, $x$ can be $1$ or $2$ and nothing else.

$\rightarrow$ So $A$ is the set of ordered pairs where the $1^{st}$ part is an element of $X$ (it is a value of $x$) and the $2^{nd}$ part is a subset of $U$.

$\rightarrow$ There are $2$ possibilities for the $1^{st}$ part, and $4$ possibilities for the $2^{nd}$ part.

$\rightarrow$ i.e. $A$ can have: $(1,\Phi ), (1, \{1 \} ) ,(1, \{2 \}), (1,\{1,2 \}), (2,\Phi ), (2, \{1 \} ) ,(2, \{2 \}), (2,\{1,2 \})$

$\rightarrow$ Here $(1,\Phi)$ will not be considered, as $1$ $\notin$ $ \Phi$.

$\rightarrow$ Similarly, $(1, \{2 \}),(2,\Phi ),(2, \{1 \} )$ won't be considered on similar grounds.

$\rightarrow$ so $A=$ $(1, \{1 \} ), (1,\{1,2 \}),,(2, \{2 \}), (2,\{1,2 \})$

$\therefore $ $\begin{vmatrix} A \end{vmatrix} = 4$

$I.$ gives answer for $n=2$ as: $\begin{vmatrix} A \end{vmatrix} = 2*2 =4$

$II.$ gives answer for $n=2$ as: $\begin{vmatrix} A \end{vmatrix} =$ $1*^{2}C_{1}$ $+ 2 * $ $^2C_2$ $=4$

$\because$ Both $I.$ and $II.$ are True

$\therefore$ Option $C$ is the right answer.


 

APPROACH 2:

 

  • To show $II.$ is correct:

$\rightarrow$ $A = \{y = (x,X)| X\ proper\ subset\ of\ U,\ x\ in X \}$.

$\rightarrow$ Lets first fix $X$. Here $X$ being proper subset of $U$, $X$ can have all values of that of a power Set of $U$.

$\rightarrow$ Lets say number of elements in $X$ is $k$.

$\because$ Number of elements of $U$ is $n$, $k$ can take values from $0$ to $n$ ($\because$ $X$ is proper subset of $U$)

$\therefore$ The number of ways of selecting $k$ from $n$ is given by $^{n}C_{k}$

$\rightarrow$ So we have $^{n}C_{k}$ choices for choosing $X$.

$\rightarrow$ Now, fixing our choice of $X$, and assuming it has $k$ elements, how many choices for $x$ are there ?

$\rightarrow$ There are $k$ different elements in $X$, so there are $k$ choices for choosing $x$

$\rightarrow$ For eg  $X= \{1,2,3 \} $, then $x$ can be $1$ or $2$ or $3$, as only these $3$ elements belong to $X$.

$\rightarrow$ So for a given $k$, there are $k* ^{n}C_{k}$ choices of $(x,X)$ such that $\begin{vmatrix} X \end{vmatrix} = k$

$\rightarrow$  So how many elements $y$ are there in total?

$\rightarrow$ Sum the above for $k =1$ to $n$. $k$ can't be $0$ because if $X$ has $0$ elements, then $x$ doesn't exist.

$\rightarrow$ i.e.$\begin{vmatrix} A \end{vmatrix}$ =  $\sum_{k=1} ^{n} k \binom{n}{k}$

 

  • To show the formula for $I.$ is correct:

$\rightarrow$ Consider choosing an element $x$ in our pair $(x,X)$. There are $n$ choices for $x$.

$\rightarrow$ Then we ask ourselves how many valid choices of $X$ are there, given $x$ ?

$\rightarrow$ $X$ is entirely defined by its elements, and we have a finite list of potential elements $(1$ to $n)$.

$\rightarrow$ For each of these, an element is either in or out, giving us $2$ possibilities each time but $x$ is already fixed to be included in $X$ for it to belong in $X$ .

$\because$ out of $n$ elements, only $x$ has $1$ choice to be included, and all the other $n-1$ elements can have $2$ possibilities as to be included or excluded in $X$.

$\because$  Its an ordered pair, we need both these conditions happening together, so using $product\ rule$ we arrive at $n*2^{n-1}$ choices for $(x,X)$.

$\because$ Both $I.$ and $II.$ are True

$\therefore$ Option $C$ is the right answer.

edited by
15 votes
15 votes

$2^{nd}$ statement is easy one

Proof for  $1^{st}$  statement using $2^{nd}$ statement

 

 

Answer:

Related questions

37 votes
37 votes
9 answers
1
32 votes
32 votes
14 answers
2
Arjun asked Feb 7, 2019
20,972 views
Let $G$ be an undirected complete graph on $n$ vertices, where $n 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to$n!$$(n-1)!$$1$$\frac{(n-1)!}{2}...
19 votes
19 votes
18 answers
3
Arjun asked Feb 7, 2019
17,951 views
The value of $3^{51} \text{ mod } 5$ is _____