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.