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.


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}}\ .$$


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


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.