# Different ways of choosing two subsets from a set

S is a set containing 10 elements. A subset P of S is chosen at random and the set S is reconstructed. Now another subset Q of S is chosen at random. Find the probabilities that-

$1)$ $P \cap Q$ contain exactly $3$ elements;
$2)$ $P \cup Q$ contain exactly $4$ elements;
$3)$ $P \cup Q = S$

• What do you mean by "the set S is reconstructed"??? – barak manos Dec 5 '16 at 16:32
• It means the elements of P are replaced. – Rohan Dec 5 '16 at 16:33
• @barakmanos Here the word "reconstruted" is used just to make sure that choosing elements for P does not affect the choosing process for Q – Sujan Dutta Dec 5 '16 at 17:07
• There is no probability associated with the question. What does choosing a subset of $S$ as random mean? Is each of the $2^{10}$ different subsets equally likely to be chosen? Or do the elements of $S$ have probabilities $p_1, p_2, \ldots, p_{10}$ and the probability of a choosing a subset $Q$ is just the probability of the event $Q$? – Dilip Sarwate Dec 5 '16 at 17:11

I’ll get you started. $S$ has $10$ elements, so it has $2^{10}=1024$ subsets. Thus, there are $2^{10}\cdot 2^{10}=2^{20}$ possible ordered pairs $\langle P,Q\rangle$ of subsets that you could pick, and they are all equally likely. To find the probability that $|P\cap Q|=3$, therefore, we need to count the ordered pairs $\langle P,Q\rangle$ such that $|P\cap Q|=3$ and divide that number by $2^{20}$.
One way to do this is to count the pairs that have each possible $3$-element intersection. Let $T$ be a $3$-element subset of $S$; we want to count the ordered pairs $\langle P,Q\rangle$ of subsets of $S$ such that $P\cap Q=T$. The trick here is to realize that each one of these pairs comes from a division of $S\setminus T$ into $3$ pairwise disjoint sets: for each element $k$ of $S\setminus T$ we must decide whether $k$ is to be in $P$, in $Q$, or in neither $P$ nor $Q$. $S\setminus T$ has $7$ elements, so we’re making a $3$-way choice $7$ times; this can be done in $3^7$ different ways. Thus, there are $3^7$ pairs $\langle P,Q\rangle$ such that $P\cap Q=T$. And there are $\binom{10}3$ possible choices for $T$, so there must altogether be $\binom{10}33^7$ ordered pairs $\langle P,Q\rangle$ of subsets of $S$ such that $|P\cap Q|=3$. The probability of getting such a pair is therefore
$$\frac{\binom{10}33^7}{2^{20}}=\frac{262,440}{1,048,576}=\frac{32805}{131072}\approx0.2503\;.$$
The other two parts can be analyzed using basically the same ideas. You’ll be dividing up either $P\cup Q$ or $S$ into $3$ parts.