Expected number of draws to find a match Suppose I have $n$ pairs of socks in a drawer, well mixed, with each pair distinct, so each sock has one unique match. I begin drawing socks one-at-a-time, at random, without replacement. Let $X_n$ be a random variable representing the number of draws necessary to find one matching pair.
Is there a nice way to describe the distribution function of $X_n$? What is its expected value? Does $\lim_{n\to\infty}\frac{E(X_n)}{n}$ exist, and if so, what is it?
It is clear that the support of the distribution is the set of integers $\{2,\ldots,n+1\}$. I have calculated the distribution and expectation for the first few values of $n$; I believe the following is without error:
$n=1$:

$\begin{matrix}x & P(X_1=x)\\ 2 & 1\end{matrix}$
$E(X_1)=2$

$n=2$:

$\begin{matrix}x & P(X_2=x)\\ 2 & \frac13\\ 3 & \frac23 \end{matrix}$
$E(X_2)=\frac83$

$n=3$:

$\begin{matrix}x & P(X_3=x)\\ 2 & \frac15\\ 3 & \frac25\\ 4 & \frac25 \end{matrix}$
$E(X_3)=\frac{16}5$

$n=4$:

$\begin{matrix}x & P(X_4=x)\\ 2 & \frac17\\ 3 & \frac27\\ 4 & \frac{12}{35}\\ 5 & \frac{8}{35} \end{matrix}$
$E(X_4)=\frac{128}{35}$

$n=5$:

$\begin{matrix}x & P(X_5=x)\\ 2 & \frac19\\ 3 & \frac29\\ 4 & \frac27\\ 5 & \frac{16}{63}\\ 6 & \frac{8}{63} \end{matrix}$
$E(X_5)=\frac{256}{63}$

From this work so far, I find it striking that the numerators are all powers of $2$. The first two probabilities in each table ($n>1$) are $\frac{1}{2n-1}$ and $\frac{2}{2n-1}$, and this is easy to show. After that.... the patterns seem a little more elusive.
I conjecture that the limit of $\frac{E(X_n)}{n}$ exists and is greater than $0$, but I don't know what it is. Its first few values, rounded, are $2, 1.333, 1.067, 0.914, 0.813$
Any ideas, insights, or references are very much appreciated. This is not a problem from a class or anything; it just comes from my own curiosity.
 A: Suppose you pick socks without replacement $k$ times, $2\leq k\leq n+1$, when you find the first match. When you pick socks the first time there are $N\equiv 2n$ ways of doing it. 
If there is to be no match during second pick, then there are $N(N-2)$ ways of picking the second sock, because for each sock picked the first time there are $(N-2)$ socks that we could pick the second time without having a match.
If there is to be no match during third pick, then there are $N(N-2)(N-4)$ ways of picking the third sock. This is because after two picks without a match, there are $(N-2)$ socks left, and for there are to be no match in the third pick there are $(N-2)-2$ choices available.
If there is to be no match during fourth pick, then there are $N(N-2)(N-4)(N-6)$ ways of picking the second sock. This is because after three picks without a match, there are $(N-3)$ socks left, and for there are to be no match in the fourth pick there are $(N-3)-3$ choices available.
Since the first match occurs on $k$-th picking, there has been no match during the previous $(k-1)$ pickings. The number of ways for there to be no match during $(k-1)$ pickings is:
\begin{align}
 &N(N-2)(N-4)...(N-2(k-2))\\
=&2^{k-1}n(n-1)(n-2)...(n-(k-2))\\
=&2^{k-1}\prod_{i=0}^{k-2}(n-i)
\end{align}
 Since you have picked $(k-1)$ distinct socks so far, to get a match on $k$-th picking we must pick one of the $(k-1)$ socks. Therefore the total number of ways to get the first match on $k$-th pick is: $N(N-2)(N-4)...(N-2(k-1))(k-1)$.
\begin{align}
(k-1)2^{k-1}\prod_{i=0}^{k-2}(n-i)
\end{align}
Since there are a total of $N(N-1)(N-2)...(N-(k-1))=\prod_{i=0}^{k-1}(2n-i)$ ways to select socks without replacement in $k$ picks the sought for probability is:
\begin{align}
\frac{(k-1)2^{k-1}\prod_{i=0}^{k-2}(n-i)}{\prod_{i=0}^{k-1}(2n-i)}
\end{align}
This formula correctly reproduces your results. Using Mathematica I get the $\lim_{n\to\infty}\frac{E[X_n]}{n}=0$.
A: Here is an alternative solution.
Let's say the first match occurs on the $X$th draw.  We would like to find $\Pr(X>k)$, i.e. the probability that there has been no match by draw $k$, for $k = 0, 1, 2, \dots ,n$. There are $\binom{2n}{k}$ possible selections of $k$ socks, all of which we assume are equally likely.  If there is no match, we must have at most one sock of each of $k$ colors.  There are $\binom{n}{k}$ ways to select the $k$ colors, and $2^k$ ways to select the socks of those colors, so $\binom{n}{k}\; 2^k$ ways in all.  So
$$\Pr(X>k) = \frac{\binom{n}{k} \; 2^k}{\binom{2n}{k}}$$
Hence 
$$E(X) = \sum_{k \ge 0}\Pr(X>k) = \sum_{k=0}^n \frac{\binom{n}{k} \; 2^k}{\binom{2n}{k}}$$
