What is the probability that $P\cap Q$ contains exactly $m(m<n)$ elements?

Question

Let $A$ be a set containing $n$ elements. A subset $P$ of the set $A$ is chosen at random. The set $A$ is reconstructed by replacing the elements of $P$, another subset $Q$ of set $A$ is chosen at random. What is the probability that $P\cap Q$ contains exactly $m$ elements, where $m<n$?

There are total $2^n$ subsets of a set having $n$ elements. But I don't have clear idea how to solve it. Please guide me.

Answer 1

The number of pairs of subsets $P,Q$ is $(2^n)^2=2^{2n}$. To construct an example where $P\cap Q$ contains exactly $m$ elements,

• choose $m$ elements for $P\cap Q$: this can be done in $C(n,m)$ ways.
• for each of the remaining $n-m$ elements, choose to place it in $P$ only, $Q$ only, or neither: this can be done in $3^{n-m}$ ways.

So the probability is $$\frac{C(m,n)3^{n-m}}{2^{2n}}\ .$$

Comment. This assumes that we can have any value of $m\le n$. In your question you said $m<n$: if you really meant this then you have to exclude the case $P=Q=A$, and the answer is $$\frac{C(m,n)3^{n-m}-1}{2^{2n}}\ .$$

Answer 2

Let $A=\left\{a_{1},a_{2},a_{3},............,a_{k},.....,a_{n}\right\}\;,$ Now for any element $a_{k}\in A\;,$

We have following possibilities

$(i)\;\;a_{k}\in P$ and $a_{k}\in Q$

$(ii)\;\;a_{k}\in P$ and $a_{k}\notin Q$

$(iii)\;\;a_{k}\notin P$ and $a_{k}\in Q$

$(vi)\;\;a_{k}\notin P$ and $a_{k}\notin Q$

So for any element $a_{k}\in A,$ There are $4$ possibilities out of which $(ii),(iii),(iv)$ are favourable

for the event that $P$ and $Q$ have no common element.

So favourable events $ \displaystyle =\binom{n}{m}\cdot 3^{n-m}$

And total number of ways is $ = 2^n\times 2^n = 4^n$

So Required probability $\displaystyle = \frac{\binom{n}{m}\cdot 3^{n-m}}{4^n}$