# probability of no matching or exactly one matching and generalization

I had the following question in a midterm today:

There are $10$ pairs of shoes. One randomly selects $8$ shoes. What is the probability that :

$\textbf{a)}$ There are no matching pairs of shoes in the selected shoes.

$\textbf{b)}$ There is exactly one matching pair of shoes.

What I wrote as a solution is :

$\textbf{a)}$ We randomly select one shoe, then two select the second one so that we don't violate the requirement we can select any of the 18 out of the 19 shoes left. Then for the third shoes that we will select we can select any of the 16 out of the 18 shoes left and so on. So we get that : $$P = \frac{18}{19}\frac{16}{18}\frac{14}{17}\frac{12}{16}\frac{10}{15}\frac{8}{14}\frac{6}{13}.$$ $\textbf{b)}$ The probability to pick exactly one pair of shoes is the probability of getting a pair of shoes and then getting no matching pairs for the remaining $18$ shoes(and to compute this we apply same logic as in part a) $$P=\frac{10}{\dbinom{20}{2}} \cdot \frac{16}{17}\frac{14}{16}\frac{12}{15}\frac{10}{14}\frac{8}{13}.$$

$\textbf{Firstly:}$ I know that my solution is quite ugly but is it right at least? If not where's the mistake?

$\textbf{Secondly:}$ Searching for duplicates of this question I found many other question similar but with some different parameters so here I am proposing the general version:

$\textbf{General Version:}$ There are $m$ pairs of shoes. One randomly selects $n$ shoes. What is the probability that there are exactly $k$ pairs of shoes in the selected ones? ($k < \lfloor n \rfloor$)

• I think that you got part (a) correct, but not part (b). – nispio Oct 31 '13 at 4:38
• The reason that part (b) is not correct is that you have imposed an order by choosing the match first. Since this is not the only way to choose 8 shoes and have two of them match, you need to add in all of the other possible orderings to make your approach valid. – nispio Oct 31 '13 at 4:50

$$\frac{\dbinom{m}{k} \dbinom{ m - k }{ n - 2k } 2^{n-2k}}{\dbinom{ 2m }{ n }}\qquad \left(\forall k\leq \left\lfloor\frac{n}{2}\right\rfloor\right)$$
There are $\binom{ 2m }{ n }$ ways to choose $n$ shoes. Assume first that we have $k=0$, then there are $\binom{ m }{ n }$ ways to choose from unique pairs, and $2^n$ ways to choose whether we take the left or right shoe from each pair.
In the case $k > 0$ there are $\binom{ m }{ k }$ ways to choose which pairs the matches come from and $\binom{ m - k }{ n - 2k }$ ways to choose which pairs the remaining non-matching pairs come from. Of the $n-2k$ non-matching pairs we selected, there are $2^{n-2k}$ ways to choose whether we take the left or right shoe from each pair.