<s>[INST] Expected value of size of subset Given a set $S$ such that $|S|=n$,
A random item is chosen randomly from $S$, and being appended to a new set $T$.
This process is being repeated $n$ times (with repetition), what is the expected value of $|T|$ ?
 [/INST] This question can also be answered by total enumeration using Stirling
numbers of the second kind.  Observe that the expectation is given by
$$\mathrm{E}[X] = n^{-n} \sum_{k=0}^n k \times {n\choose k} 
k! {n\brace k}.$$
Here we multiply the value  of the random variable by the probability,
which  is obtained  from the  fact that  a sample  with  $k$ different
entries needs a  choice of these entries from the  $n$ possibles and a
partition of  the $n$ slots into  $k$ sets whose  elements receive the
same value.  All $k!$ permutations  of the $k$ chosen values result in
a valid unique assignment.
We have
$${n\brace k} = n! [z^n] \frac{(\exp(z)-1)^k}{k!}$$
by the species equation for set partititions 
$$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$
which yields for the expectation
$$n^{-n} n! [z^n]
\sum_{k=0}^n k \times {n\choose k} 
(\exp(z)-1)^k
\\ = n^{-n} n! [z^n] n
\sum_{k=1}^n {n-1\choose k-1} 
(\exp(z)-1)^k
\\ = n^{-n} n! [z^n] n (\exp(z)-1)
\sum_{k=0}^{n-1} {n-1\choose k} 
(\exp(z)-1)^k
\\ = n^{-n} n! [z^n] n (\exp(z)-1) \exp((n-1)z)
= n n^{-n} n! [z^n] (\exp(nz)-\exp((n-1)z))
\\ = n n^{-n} (n^n - (n-1)^n)
\\ = n \left(1 - \left(1-\frac{1}{n}\right)^n\right)
\sim n \left(1 - \frac{1}{e}\right).$$
Now we can also compute higher moments with this, 
the variance for example.
We first compute the expectation of $X(X-1)$, getting
$$\mathrm{E}[X(X-1)] =
n^{-n} \sum_{k=0}^n k (k-1) \times {n\choose k} 
k! {n\brace k}
\\ = n^{-n} n! [z^n] n (n-1)
\sum_{k=2}^n {n-2\choose k-2} 
(\exp(z)-1)^k
\\ = n^{-n} n! [z^n] n (n-1) (\exp(z)-1)^2
\sum_{k=0}^{n-2} {n-2\choose k} 
(\exp(z)-1)^k
\\ = n^{-n} n! [z^n] n (n-1) (\exp(z)-1)^2 \exp((n-2)z).$$
Extracting coefficients we obtain
$$n (n-1) n^{-n} (n^n - 2(n-1)^n + (n-2)^n)
= n(n-1) \left(1-2\left(1-\frac{1}{n}\right)^n
+\left(1-\frac{2}{n}\right)^n\right)
\\ \sim 
n(n-1) \left(1-\frac{2}{e}+\frac{1}{e^2}\right).$$
We thus get for the variance
$$\mathrm{Var}[X] = \mathrm{E}[X^2] - \mathrm{E}[X]^2
\\ = n(n-1) \left(1-2\left(1-\frac{1}{n}\right)^n
+\left(1-\frac{2}{n}\right)^n\right)
\\ + n\left(1-\left(1-\frac{1}{n}\right)^n\right)
- n^2\left(1-\left(1-\frac{1}{n}\right)^n\right)^2
\\ = n^2 \left(\left(1-\frac{2}{n}\right)^n
- \left(1-\frac{1}{n}\right)^{2n}\right)
\\ + n \left(\left(1-\frac{1}{n}\right)^n
- \left(1-\frac{2}{n}\right)^n \right).$$
The asymptotic expansion then yields
$$\mathrm{Var}[X] \sim n \left(\frac{1}{e}-\frac{2}{e^2}\right).$$
Addendum. We need the second term rather than the constant term in
the asymptotic expansion of the factor on $n^2.$
We get for the first term in the difference
$$\exp\left(n\log\left(1-\frac{2}{n}\right)\right)
= \exp\left(-\sum_{q\ge 1} \frac{2^q}{n^{q-1} q}\right)
\\ = \sum_{k\ge 0} \frac{(-1)^k}{k!}
\left(\sum_{q\ge 1} \frac{2^q}{n^{q-1} q}\right)^k.$$
This yields for the constant term
$$\sum_{k\ge 0}  \frac{(-1)^k}{k!} 2^k = \frac{1}{e^2}.$$
We get for the next term
$$\frac{1}{n} 
\sum_{k\ge 0} \frac{(-1)^k}{k!} 
{k\choose 1} 2\times 2^{k-1}
= -\frac{2}{n} 
\sum_{k\ge 1} \frac{(-1)^{k-1}}{(k-1)!}  2^{k-1}
= -\frac{2}{n} \frac{1}{e^2}.$$
For the second term in the difference we have
$$\exp\left(2n\log\left(1-\frac{1}{n}\right)\right)
= \exp\left(-2\sum_{q\ge 1} \frac{1}{n^{q-1} q}\right)
\\ = \sum_{k\ge 0} \frac{(-2)^k}{k!}
\left(\sum_{q\ge 1} \frac{1}{n^{q-1} q}\right)^k.$$
This time we get for the constant term
$$\sum_{k\ge 0}  \frac{(-2)^k}{k!} = \frac{1}{e^2}$$
and for the next term
$$\frac{1}{n} 
\sum_{k\ge 0} \frac{(-2)^k}{k!} 
{k\choose 1} \frac{1}{2} \times 1^{k-1}
= -\frac{1}{n} 
\sum_{k\ge 1} \frac{(-2)^{k-1}}{(k-1)!}
= -\frac{1}{n} \frac{1}{e^2}.$$
The difference then yields for the variance 
$$n^2 \left(-\frac{1}{n} \frac{1}{e^2}\right)
+ n\left(\frac{1}{e}-\frac{1}{e^2}\right)$$
which is the desired result.
</s>