I am trying to solve the following counting problem in Feller's probability book. I checked my answer against that given in the book. My answer to part (a) of the problem is correct (b) but I am difficulty deriving the expression for part (b). Here is my attempt.
Part(a) of the problem was also answered here – Probability/Combinatorics Problem. A closet containing n pairs of shoes.
- A closet has $n$ pairs of shoes. If $2r$ shoes are chosen at random (with $2r<n$), what is the probability that there will be (a) no complete pair, (b)exactly one complete pair (c) exactly two complete pairs among them?
Solution.
The sample space S has ${2n \choose 2r}$ sample points.
(a) No complete pair:
Select one of $2n$ shoes. The second shoe can be one of $2n-2$ shoes. The third shoe can be one of $2n-4$ shoes. The $k$'th shoe can be one of $2n-(2k-2)$ shoes.
The $2r$th shoe can be one of $2n-(4r-2)$ shoes. These $2r$ shoes can be permuted in (2r)! ways. As the order does not matter,
$$n(\text{No complete pair})=2^{2r}\frac{n!}{(n-2r)!(2r)!}=2^{2r}{n \choose 2r}$$
$$P(\text{No complete pair})=\frac{2^{2r}{n \choose 2r}}{{2n \choose 2r}}$$
(b) Exactly one complete pair.
Select one of $2n$ shoes. This shoe must have a pair, so that could be selected in only $1$ way. The third shoe can be one of $(2n-2)$ shoes, $k$th shoe is one of 2n-(2k-4). The $2r$th shoe is one of $2n-(4r-4)$. Also, since order is not important, we are overcounting by a factor of $(2r)!$.
$$\begin{alignedat}{1}n(\text{Exactly one pair}) & =(2n)\cdot(2n-2)\cdot(2n-4)\cdot(2n-(4r-4))/(2r)!\\
& =2^{2r-1}\frac{n!}{(n-2r+1)!(2r)!}\\
& =2^{2r-2}\frac{(n-1)!}{(n-2r+1)!(2r-1)!}\cdot\frac{n}{r}
\end{alignedat}$$
The correct solution to part (b) of this problem in the book is:
$$\frac{n{{n-1}\choose{2r-2}}2^{2r-2}}{{2n}\choose{2r}}$$
Best Answer
(a) $\ddot\smile\checkmark$, you are correct, because you are selecting $2r$ distinct pairs and taking one shoe from of each of them.
$$P(\text{no completes}) = \dfrac{~2^{2r}\dbinom n {2r}~}{\dbinom{2n}{2r}}$$
(b) $\ddot{\frown}\times$ The book is correct, because you are selecting one complete pair from $n$, and from the $n-1$ pairs selecting $2r-2$ distinct pairs and taking just one shoe from each of those. There is no order to these selections.
$$P(\text{exactly one complete}) = \dfrac{2^{2r-2}\dbinom{n}{1}\dbinom{n-1}{2r-2}}{\dbinom{2n}{2r}}$$
[PS: Your logic of selecting one of 2n shoes, then its pair, over counts cases, so is wrong right from the start.]
(c) $\ddot\sim?$ Now can you apply the same principle to find the probability of selecting exactly two complete pairs?