How to calculate the expected number of distinct items when drawing pairs? Suppose I have a set $\mathcal{S}$ of $N$ distinct items. Now consider the set $\mathcal{P}$ of all possible pairs that I can draw from $S$. Naturally, $|\mathcal{P}| = \binom{N}{2}$. Now when I draw $k$ items (pairs) from $\mathcal{P}$ with a uniform distribution, what is the expected number of distinct items from $S$ in those $k$ pairs?
P.S.: I also asked this question over at stats, but got no answers so far, so I am trying here. Thanks for your time!
Edit I pick the pairs without replacement.

For choosing without replacement, here is an exact answer.  Assuming $n \geq 2$, so that there is at least one pair, and $1 \leq k \leq \binom{n}{2}$, so that you're choosing at least one pair but not more than the total number of pairs, the expected value is  
$$n - \left(\frac{n^2 - 3n - 2k + 4}{n-1}\right) \frac{\binom{\binom{n}{2} - n + 1}{k-1}}{\binom{\binom{n}{2} - 1}{k-1}}.$$
We can assume that we are choosing pairs in order.  Let $X_k$ be the number of distinct items from $S$ through $k$ pairs.  Let $Y_i$ be the number of items in the $i$th pair that did not appear in any of the previous pairs.  So $X_k = \sum_{i=1}^k Y_i$.
Now, $Y_i$ is either 0, 1, or 2.  Since there are $\binom{n}{2} - n + 1$ pairs that do not contain a given item and $\binom{n}{2} - 2n + 3$ pairs that do not contain either of two given items, we have
$$P(Y_i = 1) = \frac{\binom{\binom{n}{2} - n + 1}{i-1} + \binom{\binom{n}{2} - n + 1}{i-1} - 2 \binom{\binom{n}{2} - 2n + 3}{i-1}}{\binom{\binom{n}{2} - 1}{i-1}}$$
and
$$P(Y_i = 2) = \frac{\binom{\binom{n}{2} - 2n + 3}{i-1}}{\binom{\binom{n}{2} - 1}{i-1}}.$$
Thus 
$$E[Y_i] = 2\frac{\binom{\binom{n}{2} - n + 1}{i-1}}{\binom{\binom{n}{2} - 1}{i-1}}.$$
It can be proved by induction that 
$$\sum_{i=0}^k \frac{\binom{M}{i}}{\binom{N}{i}} = \frac{(N+1)\binom{N}{k} - (M-k)\binom{M}{k}}{(N+1-M)\binom{N}{k}}.$$
Thus 
$$E[X_k] = \sum_{i=1}^k E[Y_i] = 2\sum_{i=1}^k \frac{\binom{\binom{n}{2} - n + 1}{i-1}}{\binom{\binom{n}{2} - 1}{i-1}} $$ 
$$= 2\frac{(\frac{n(n-1)}{2}-1+1)\binom{\binom{n}{2}}{k-1} - (\frac{n(n-1)}{2} - n + 1 - k + 1)\binom{\binom{n}{2} - n + 1}{k-1}}{(\binom{n}{2} - 1+1-\binom{n}{2} + n - 1)\binom{\binom{n}{2} - 1}{k-1}}$$
$$= \frac{n(n-1)\binom{\binom{n}{2}}{k-1} - (n^2 - 3n - 2k + 4)\binom{\binom{n}{2} - n + 1}{k-1}}{(n - 1)\binom{\binom{n}{2} - 1}{k-1}}$$
$$= n -\frac{(n^2 - 3n - 2k + 4)\binom{\binom{n}{2} - n + 1}{k-1}}{(n - 1)\binom{\binom{n}{2} - 1}{k-1}}.$$
