# Probability/Combinatorics Problem. A closet containing n pairs of shoes.

A closet contains n pairs of shoes. If 2r shoes are chosen at random, (where 2r < n), what is the probability that the chosen shoes will contain no matching pair?

I have tried thinking about this problem on my own and have not gotten much farther than deducing that there are ${2n \choose 2r}$ possible combinations that could be chosen.

When I did some searching I found two different solutions for this same problem and I am having trouble discerning which would be correct. No explanation is given with either solution and I am relatively new to probability and combinations so any help from someone with a bit more experience would be much appreciated.

Solution 1:
The probability is computed as $${n \choose 2r}2^{2r}/{2n \choose 2r}$$

Solution 2:
The probability is computed as $${n \choose r}2^{r}/{2n \choose 2r}$$

If anyone could tell me which of these two is correct and why. I understand that the probability is given as a certain number of combinations out of the total number of possible combinations. What do the two different factors in the numerators represent, and how do they differ in the two solutions?

-

We are choosing $2r$ shoes. How many ways are there to avoid a pair? The pairs represented in our sample can be chosen in $\binom{n}{2r}$ ways. From each chosen pair, we can choose the left shoe or the right shoe. There are $2^{2r}$ ways to do this. So of the $\binom{2n}{2r}$ equally likely ways to choose $2r$ shoes, $\binom{n}{2r}2^{2r}$ are "favourable."

Another way: A perhaps more natural way to attack the problem is to imagine choosing the shoes one at a time. The probability that the second shoe chosen does not match the first is $\frac{2n-2}{2n-1}$. Given that this has happened, the probability the next shoe does not match either of the first two is $\frac{2n-4}{2n-2}$. Given that there is no match so far, the probability the next shoe does not match any of the first three is $\frac{2n-6}{2n-3}$. Continue. We get a product, which looks a little nicer if we start it with the term $\frac{2n}{2n}$. So an answer is $$\frac{2n}{2n}\cdot\frac{2n-2}{2n-1}\cdot \frac{2n-4}{2n-2}\cdot \frac{2n-6}{2n-3}\cdots \frac{2n-4r+2}{2n-2r+1}.$$ This can be expressed more compactly in various ways.

-

\begin{align*} & 2n \times (2n - 2) \times (2n - 4) \times (2n - 6) \times \cdots \times (2n - 4r + 2) \\ =& 2^{2r} \times n \times (n - 1) \times \cdots \times (n - 2r + 1) \\ =& 2^{2r} \times \frac{ n! }{ (n - 2r)! } \end{align*}
But $\frac{ n! }{ (n - 2r)! } \Leftrightarrow \binom{n}{2r}$.