From the "sock-matching problem" over on SO, given a pile of $2N$ socks, each having one and only one matching sock in the pile, and drawing $N$ socks randomly and without replacement from this pile, I need to determine the probability $P(N)$ that all $N$ socks are different and thus cannot be matched with any sock already drawn.
The $N+1$th sock, by definition of the problem, will match one and only one sock; therefore, this scenario represents the worst-case of an "intelligent" algorithm that compares each new sock to an array of already-chosen, unmatched socks; each sock in the array so far will have been compared to every other sock, requiring $(N-1)N/2$ comparisons for a complexity of $O(N^2)$. The worst-case from there, given a simple array of the drawn socks and no information about the location of each sock in that series, is that the remaining socks are drawn in reverse order to how their matches were originally drawn, so the $N+1$th sock matches the sock previously drawn (and all socks would be scanned left to right to find its match at the very last sock of the first $N$ drawn), producing an overall complexity of the entire algorithm of N(N-1). This worst-case is extremely unlikely; I want to know how unlikely, because this algorithm's worst case matches the worst case of the "naive" method, where one sock is drawn at random and then all other socks in the pile are compared to find its match; the worst case is, for each sock, you find the match with the last sock remaining in the pile, which is $N(2N-2)/2 = N(N-1)$ comparisons.
Obviously, the first sock drawn has no match. The second sock is drawn from the remaining pool of $2N-1$ socks, in which there is one possible match for the already drawn sock. The third sock is drawn from $2N-2$ socks, and there are two matches for already-drawn socks. So, the probability in exploded version of drawing $N$ unique single socks from a pile of $N$ matched pairs is:
$P(N) = 1 * (1-(\dfrac{1}{2N-1})) * (1-(\dfrac{2}{2N-2})) * (1-(\dfrac{3}{2N-3})) * … * (\dfrac{3}{N+3}) * (\dfrac{2}{N+2}) * (\dfrac{1}{N+1})$
This can then be multiplied by the result of the following series to determine the probability of the absolute worst-case scenario of drawing $N$ unmatched socks and then drawing each matching sock in reverse order:
$P(N') = \dfrac{1}{N} * \dfrac{1}{N-1} * \dfrac{1}{N-2} * … * \dfrac{1}{3} * \dfrac{1}{2} * \dfrac{1}{1}$
If someone whose head hurts less than mine from a 12-hour day could digest these into series sums, I'd appreciate it.
Best Answer
First,
$$\prod_{k=1}^{N-1}\left(1-\frac{k}{2N-k}\right)=\prod_{k=1}^{N-1}\frac{2N-2k}{2N-k}=\prod_{k=1}^{N-1}\frac{2(N-k)}{N+(N-k)}=\prod_{k=1}^{N-1}\frac{2k}{N+k}=\frac{2^{N-1}(N-1)!}{(2N-1)^{\underline{N-1}}}\;.$$
You’re multiplying this by $\dfrac1{N!}$, so you end up with $$\frac{2^{N-1}(N-1)!}{N!(2N-1)^{\underline{N-1}}}=\frac{2^{N-1}(N-1)!}{(2N-1)!}=\frac{2^{N-1}}{(2N-1)^{\underline N}}\;,$$
where $x^{\underline n}=x(x-1)(x-2)\ldots(x-n+1)$ is the falling factorial. This can also be expressed as
$$\frac{2^{N-1}(N-1)!}{(2N-1)!}=\cdot\frac{2^{N-1}N!(N-1)!}{(2N-1)!}\cdot\frac{2N}{2N}=\frac{2^N}\binom{2N}N^{-1}\;.$$