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?
 A: To avoid the ambiguity of a terminology that refers to everything as an "item," let's suppose the set $S$ consists of $n$ distinct "letters."  And, because this is a pretty generalization of the Birthday Paradox, let's generalize it a little further and set $P$ to be the set of all $r$-letter words having all distinct letters.  The question as stated corresponds to $r=2$.  We ask more generally

What is the expected number of distinct letters found in the $r k$-letter word obtained by concatenating $k$ random $r$-letter words of distinct letters?

We can compute this in three stages:


*

*For any $m$, $r \le m \le n$, find the proportion of the $k$-fold $r$-letter words having $m$  or fewer distinct letters.

*From this obtain the probability $p_{n,k,r}(m)$ of exactly $m$ distinct letters.

*Compute the expected number of letters by summing $m p_{n,k,r}(m)$ over $m$ (from $r$ to $n$).
We find the proportions in #1 with a polynomial expansion.  Let $f_r(x_1, x_2, \ldots, x_n)$ be the average of all words of length $r$ in which the letters are distinct.  For example, 
$$f_2(x_1, x_2, x_3) = \left( x_1 x_2 + x_2 x_1 + x_2 x_3 + x_3 x_2 + x_1 x_3 + x_3 x_1 \right)/6 \text{.}$$
The $k^\text{th}$ power of this (computed as a polynomial) displays the probabilities with which which words can be formed by a $k$-fold concatenation.  For example, inspection of the coefficients of
$$f_2(x_1, x_2, x_3)^2 = \left( x_1^2 x_2^2 + x_2^2 x_3^2 + x_1^2 x_3^2 + 2 x_1^2 x_2 x_3 + 2 x_1 x_2^2 x_3 + 2 x_1 x_2 x_3^2 \right) / 9 $$
shows that the chance of forming a word with two $x_1$'s and two $x_2$'s (which can occur in four ways out of the 36 possible ways: $x_1x_2x_1x_2$, $x_1x_2x_2x_1$, $x_2x_1x_1x_2$, and $x_2x_1x_2x_1$) is 1/9.
When we set some of the $x_i$ equal to zero, they drop out of $f_r^k$ altogether, and when we set the remaining $x_i$ equal to one, what remains is the sum of their coefficients.  Thus we could hope to find the probability of having $m$ distinct letters by setting exactly $m$ of the $x_i$ to one (and the remainder to zero) and summing the value of $f_r^k$ over all such possibilities.  (This is easily done because the symmetry of $f_r$ implies all these values are equal, so we need only compute $f_r^k(1,\ldots,1,0,\ldots,0)$ and multiply that by ${n}\choose{m}$.)  Unfortunately, this also over-counts words having fewer than $m$ distinct letters, so we have to apply the Principle of Inclusion-Exclusion to extract the desired value.  The punchline is that $f_r$ is easy to evaluate; when we set $n-m$ of its arguments to $0$, there remain ${n}\choose{m}$ terms, all of which will evaluate to $1$, whence
$$f_r^k(1,\ldots,1,0,\ldots,0) = {{m}\choose{k}} / {{n}\choose{k}}.$$
Putting this together gives
$$p_{n,k,r}(m) = {{n}\choose{m}} \sum_{j=0}^{m-r}{(-1)^j {{m}\choose{m-j}} {{m-j}\choose{r}}^k } / {{n}\choose{r}}^k \text{.}$$
The expectation equals
$$\mathbb{E}[\text{# distinct letters}] = \sum_{m=r}^n{p_{n,k,r}(m) m}.$$
This looks like an expression that is unlikely to simplify.  Its calculation requires $O(n^2)$ effort.  When $k$ is small, this can be reduced to $O(n r k)$ by dynamic programming using a recursive relationship between the probability distribution for $k$ and the probability distribution for $k+1$.  The recursion is obtained by considering how $m+r$ distinct letters can arise in a $k+1$-fold concatenation: either $r$ distinct letters are adjoined to a word of $m$ distinct letters, or $r-1$ distinct letters are adjoined to a word of $m+1$ distinct letters, ..., or no distinct letters are introduced to a word of $m+r$ distinct letters.  Rather than write down this recursion generally, I'll display the case $r=2$:
$$\eqalign{
p_{n,k+1,2}(m+2) &= \Bigl[ {{n-m}\choose{2}} p_{n,k,2}(m) \cr
&+ (m+1)(n-m+1)p_{n,k,2}(m+1) \cr
&+ {{m+2}\choose{2}} p_{n,k,2}(m+2) \Bigr] / {{n}\choose{2}}
}\text{.}$$
The dynamic program computes the entire distribution for the case $k=1$ and then uses this recursion to compute it for $k=2, \ldots$ up to the desired value.
