1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Your mistake lies in the fact that you found the number of non-negative integral solutions to the equation $x+y=k-2$ Since the elements are not identical, doing so is incorrect. $\endgroup$ – MathGod Jul 6 '15 at 13:30
3
$\begingroup$

In how many ways can two distinct subsets of the set A of k (k≥3) elements be selected so that they have exactly two common elements?

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)$$

$\endgroup$
  • $\begingroup$ It looks like you meant for the rest of the $\color{red}{k - 2}$ elements, we have $3$ choices. $\endgroup$ – N. F. Taussig Jul 7 '15 at 9:26
3
$\begingroup$

You are assuming that all the elements of $A$ have to be in one subset or the other, which is not required. After you put the two elements in both $P$ and $Q$, each element can go in $P$, in $Q$, or neither independently. That gives a factor $3$ for each of the $k-2$ remaining elements. You divide by $2$ because you are double counting-each assignment of elements to $P$ and $Q$ is counted again in reversing the two sets. The $-1$ comes because you didn't doulble count the case where both $P$ and $Q$ are empty. I leave it to you to put it all together.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.