3
$\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$
1
  • 4
    $\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
    Commented Jul 6, 2015 at 13:30

2 Answers 2

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$
1
  • $\begingroup$ It looks like you meant for the rest of the $\color{red}{k - 2}$ elements, we have $3$ choices. $\endgroup$ Commented Jul 7, 2015 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .