Probability that two different subsets sharing exactly two elements

combinatoricsprobability

Given the set $S$ that is the set of all subsets of $\{1, 2, \ldots, n\}$. Two different sets are chosen at random from $S$. What is the probability that
the two subsets share exactly two equal elements?

My attempt

I found that the universal set $\Omega = \dfrac{2^n\left(2^n-1\right)}{2}$

Then I tried to find the number of ways to select two subsets sharing two equal elements:

The number of ways to choose one subset that contains $i, j$ is $2^{n-2}$.

The number of ways to choose another subset that contains $i, j$ and is different from the previous is: $\sum{2^{n-k-1}}$

However, I failed to put those two together to obtain correct result. I wonder whether there is another approach to this problem or how my method could have been continued.

Thanks in advance.

Best Answer

For each element $x$ in $\{1,2,\dots,n\}$ and choosing two subsets $A,B$ of this there are four options with the following caveats.

  • $x\in A$ and $x\in B$ (we desire at least two such $x$)
  • $x\in A$ and $x\notin B$
  • $x\notin A$ and $x\in B$ (we require at least one such $x$ in this or the previous to ensure the two selected sets were different)
  • $x\notin A$ and $x\notin B$

Our sample space is then of size $4^n-2^n$, getting this as there are $4$ choices for each of the $n$ elements in the set and applying multiplication principle and subtracting away the selections where the second two cases both had zero elements and the subsets then are equal. (Dividing by two is fine if you insist on working with the two subsets as indistinguishable, however I see no reason to enforce that).

Now... let us count the number of ways in which strictly fewer than two elements wound up in the first case. Well... that would be exactly one element ending in the first case or zero elements ending in the first case.

If exactly one element ended in the first case, pick which it was and then pick how to distribute the rest of the elements, again keeping in mind the restriction on the second and third cases. This gives $n(3^{n-1}-1^{n-1})$

Finally, with no elements ending in the first case, that gives $3^n-1^n$

Putting this all together, our final desired probability that our two subsets share at least two equal elements is:

$$1-\frac{n(3^{n-1}-1)+(3^n-1)}{4^n-2^n}$$

In the case of desiring exactly two equal elements, simply pick which two elements are used in the first case, then with the remaining elements avoid having sent them all to the fourth case.

This gives probability:

$$\frac{\binom{n}{2}(3^{n-2}-1)}{4^n-2^n}$$

Related Question