Question

In how many ways can two distinct subsets of the set A of k (${\text{k}} \geqslant 2$) elements be selected so that they have exactly two common elements.

Answer 1

Hint: In this question the concept of permutations and combinations will be used. We need to apply logic and general algebra to proceed through the problem. We will first assume the set A and select two elements out of it. Then we will arrange the rest of the elements in the two subset, which will give us the answer. In order to select r unique things from a total number of n things, the number of ways are-
${}_{}^{\text{n}}{\text{C}}_{\text{r}}^{} = \dfrac{{{\text{n}}!}}{{\left( {{\text{n}} - {\text{r}}} \right)!{\text{r}}!}}$

Complete step-by-step answer:
We have to form two subsets of set A that have exactly two common elements. We will assume that-
${\text{A}} = \left\{ {{{\text{a}}_1},\;{{\text{a}}_2},\;...,\;{{\text{a}}_{\text{k}}}} \right\}$
Let B and C be two subsets of A such that they have two common elements. So, first we will find the number of ways in which the two common elements in B and C can be selected. So, we can select 2 things from a total of k things as-
${}_{}^{\text{k}}{\text{C}}_2^{} = \dfrac{{{\text{k}}!}}{{\left( {{\text{k}} - 2} \right)!2!}} = \dfrac{{{\text{k}}\left( {{\text{k}} - 1} \right)}}{2}$
Now, the rest of the (k - 2) elements in the set A have three options each. Either they can go only in B, only in C or neither of the two subsets. So, the total number of cases for arranging all the remaining elements are-
$3 \times 3 \times 3 \times ...\left( {{\text{k}} - 2\;times} \right) = {3^{{\text{k}} - 2}}$
But this includes one case where all the remaining elements go neither in B nor in C. This means that B and C will be the same sets with the two elements that are common to each other. But we need to find only distinct subsets of A so this case will be rejected as-
${3^{{\text{k}} - 2}} - 1$

Now these cases have pairs of subsets which are common to each other. For example,
${\text{B}} = \left\{ {{{\text{a}}_1},\;{{\text{a}}_2},\;{{\text{a}}_3}} \right\}\;and\;{\text{C}} = \left\{ {{{\text{a}}_1},\;{{\text{a}}_2},\;{{\text{a}}_4}} \right\}$
${\text{B}} = \left\{ {{{\text{a}}_1},\;{{\text{a}}_2},\;{{\text{a}}_4}} \right\}\;and\;{\text{C}} = \left\{ {{{\text{a}}_1},\;{{\text{a}}_2},\;{{\text{a}}_3}} \right\}\;$
These two cases are the same, hence we need to divide the total number of ways by two as-
$\dfrac{{{3^{{\text{k}} - 2}} - 1}}{2}$

Hence, the total number of ways two distinct subsets of the set A of k (${\text{k}} \geqslant 2$) elements be selected so that they have exactly two common elements are-
$\dfrac{{{\text{k}}\left( {{\text{k}} - 1} \right)}}{2} \times \dfrac{{{3^{{\text{k}} - 2}} - 1}}{2}$
This is the required answer.


Note: There is no direct method to solve this problem. We need to form the equations according to the question, and simplify it using general algebra. One common mistake is that students often forget the formula for combinations and permutations, which should be remembered. Also, we have been given that the subsets should be distinct. We often neglect this word, and this results in the wrong answer.