2

Given a set with $m$ pairs of shoes and $l$ singletons (missing pairs), and assuming we draw without replacement $n$ shoes, what is the probability that we will obtain $k$ pairs?

This is an extension to the problem discussed here, where the set was constrained to having only pairs.

The formula for that simpler case as described by the author is:

$$\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)$$

I was able to work some parts that should change:

  • The total number of possible draws is now $\binom{ 2m + l }{ n }$

  • The total number of possible unique elements is $\binom{ m - k + l}{n - 2k}$

The problem is that these unique elements can come from either pairs (which means we can pick either the left or the right one) or from singletons (no such choice). We should double the former but not the latter.

If we knew whether the non-matching items were singletons, I think the problem would be more straightforward. But not knowing that, I am not sure how to tackle it.

Any suggestions?

Michael Hardy
  • 1
RV1994
  • 23

1 Answers1

1

You can sum over the number $j$ of non-matching shoes that are singletons to obtain a count of

$$ \frac{\binom mk}{\binom{2m+l}n}\sum_{j=0}^{n-2k}\binom{m-k}{n-2k-j}\binom lj2^{n-2k-j}\;. $$

I don’t think this sum can be simplified (other than by writing it as a generalized hypergeometric series).

joriki
  • 238,052