# Choosing two sets with k mutual elements

I am struggling with the following question:

We have N balls. We first draw n of them and write their numbers.
We then put them all back and draw another m balls. What is the sample space?
What is the probability of drawing two sets with exactly k elements?


So here's what I have so far:

The sample space is $$|\Omega|=\{(A,B)\colon A,B\subseteq [1..N],|A|=n,|B|=m\},|\Omega|=\binom{N}{n}\cdot \binom{N}{m}$$

And as for drawing two sets with exactly k elements i didn't really use the sample space defined, but rather just counted how many pairs of such sets exists and I came up with $$PAIRS=\binom{N}{k}\binom{N-k}{n-k}\binom{N-n}{m-k}$$ so the probability is $\frac{1}{PAIRS}$

Am I right? If not, where is my mistake? thanks!

• What does "drawing two sets with exactly $k$ elements" mean? Does it mean that there are exactly $k$ elements in the union of the two sets? – bof Nov 6 '13 at 9:12
• @bof: Judging from the title and the displayed calculation, it should be What is the probability of drawing two sets with exactly k elements in common? – Brian M. Scott Nov 6 '13 at 9:25
• @BrianM.Scott The title and the displayed calculation reflect the OP's understanding of the question. But the actual question is "What is the probability of drawing two sets with exactly k elements." Not as clear as I'd like (hence my comment), but as it stands, "between them" is a more natural interpretation that "in common" IMHO. – bof Nov 6 '13 at 9:59
• @bof: But we also don’t know for sure that the question has been quoted exactly rather than paraphrased. – Brian M. Scott Nov 6 '13 at 10:06
• I guessed that the stuff in a different font was copied and pasted, probably from the original source. No way to be sure, which is why I asked OP for clarification. – bof Nov 6 '13 at 10:21

• From all the possible combinations: $\binom{N}{k}$, you only need 1 valid (the one that matches the 1st draw. This is a possibility of $P3=\frac{1}{\binom{N}{k}}$
$P=P1*P2*P3= \frac{k}{N}*\frac{k}{N}*\frac{1}{\binom{N}{k}}$
For the probability part of the question, think of it as a hypergeometric distribution question. After you've drawn the $n$ balls and put them back, you've broken the $N$ balls into two groups: the n you drew, and the $(N-n)$ you didn't. Now when you pick you $m$ balls in the second round, you want to: pick $k$ balls from the group of $n$, and $(m-k)$ from the group of $(N-n)$. So that's $\frac{\left( \stackrel{n}{k} \right) \left( \stackrel{N-n}{m-k} \right)}{\left( \stackrel{N}{m} \right)}$