In how many ways can two distinct subsets of the set $\text{A}$ of $k$ $(k \geq 3)$ elements be selected so that they have exactly two common elements?
I started by choosing two elements (that are common) in $\dbinom{k}{2}$ ways. For the rest of the elements, I assumed $x$ elements in subset $\text{P}$ and $y$ elements in subset $\text{Q}$. Then I found the number of non-negative integral solutions to the equation $$x+y=k-2$$
which is equal to $\dbinom{k-2+2-1}{2-1} = \dbinom{k-1}{1} = k-1$
Therefore, the total number of ways to select subsets $= \dbinom {k}{2} \times (k-1)$
However, the answer given in my book is $\dfrac{k(k-1)}{4} \cdot (3^{k-2}-1)$
Any help will be appreciated.
Thanks.
Best Answer
Choose two elements for intersection: $$\binom k2=\frac{k(k-1)}2$$
Rest $k-2$ elements have 3 choices: $A-B,B-A,(A\cup B)'$ and minus for one case where all go to $(A\cup B)'$ because then $A=B$: $$3^{k-2}-1$$
Since we counted: $(A,B)$ twice as $(A,B),(B,A)$, divide by 2: $$T=\frac{k(k-1)}4(3^{k-2}-1)$$