Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer

I'm not sure about the answer here.

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

share|cite|improve this answer
Please make sure that I did not change the content of your answer :) – Eric Stucky Jan 7 '14 at 8:18
I am not able to comment, but the answer to James's query is that he has counted all permissable ordered selections of shoes, when what we want to count are permissable sets. So either the numerator or denominator should be changed. Dividing the number of permissable ordered selections by the number of orderings, (2r)!, will give the desired binomial term. Alternatively you can change the denominator to be (2n!)/(2n-2r)! To reflect all possible ordered selections of size 2r. – user2428096 Jan 9 '14 at 12:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.