Question

Let $S=\{1,2,3,\dots ,n\}$ and $A=\{(a,b)|1\le a,b\le n\}=S\times S$. A subset $B$ of $A$ is said to be a good subset if $(x,x)\in B$ for every $x\in S$. Then the number of good subsets of $A$ is

• A. $1$
• B. $2^n$
• C. $2^{n(n-1)}$
• D. $2^{n^2}$

Answer 1

Answer: (C)

$2^{n(n-1)}$

Number of elements in $B$ $=n\times n=n^2$

No of elements of type $(x,y)$ $=n^2-n$

After choosing $n$ elements

We can choose any number of elements from $n^2-n$ elements

$\therefore$ Number of subsets $=C_0^{n^2-n}+C_1^{n^2-n}+C_2^{n^2-n}...........C_{n^2-n}^{n^2-n}$

As $C_0^n+C_1^n+C_2^n.....C_n^n=2^n$

$\Rightarrow C_0^{n^2-n}+C_1^{n^2-n}+C_2^{n^2-n}...........C_{n^2-n}^{n^2-n}=2^{n^2-n}$

So option $C$ is correct