We are choosing 2 2 r shoes. How many ways are there to avoid a pair? The pairs represented in our sample can be chosen in (2) ( n 2 r ) ways. From each chosen pair, we can choose the left shoe or the right shoe. There are 22 2 2 r ways to do this. So of the (22) ( 2 n 2 r ) equally likely ways to choose 2 2 r shoes, (2)22 ( n 2 r ) 2 2 r 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 2−22−1 2 n − 2 2 n − 1 . Given that this has happened, the probability the next shoe does not match either of the first two is 2−42−2 2 n − 4 2 n − 2 . Given that there is no match so far, the probability the next shoe does not match any of the first three is 2−62−3 2 n − 6 2 n − 3 . Continue. We get a product, which looks a little nicer if we start it with the term 22 2 n 2 n . So an answer is 22⋅2−22−1⋅2−42−2⋅2−62−3⋯2−4+22−2+1. 2 n 2 n ⋅ 2 n − 2 2 n − 1 ⋅ 2 n − 4 2 n − 2 ⋅ 2 n − 6 2 n − 3 ⋯ 2 n − 4 r + 2 2 n − 2 r + 1 . This can be expressed more compactly in various ways.
