Expected proportion of the sample when bootstrapping suppose you have a sample of size $N$ that for some reason you want to bootstrap to produce a sample of size $M$. I am trying to produce a closed form solution for the expected proportion of the sample that will be present when I bootstrap a sample. I have not been able to produce it, however, I have used Matlab to come up with a numerical approximation.
I took a sample of size 100 and produced bootstrap 300 samples of sizes varying from 1 to 500. For a fixed bootstrap sample size, I later estimated the mean proportion of the original sample that got into the bootstrapped sample by averaging over the number of unique values. This is what I got:

Any ideas on how to produced the closed form for this number?
 A: This is related to collision-counting in the birthday problem.
Imagine you walk into a room of $k$ people. The probability at least one shares a birthday with you is  $q(k;n) = 1 - \left( \frac{n-1}{n} \right)^k$, where $n$ is the number of different birthday slots (days in the year).
The expected number you add to the total number of different birthdays in the room when you walk in is therefore $1-q(k;n)=\left( \frac{n-1}{n} \right)^k$
So by the law of iterated expectations, the expected number of different birthdays after $m$ people have entered is 
$\sum_{i=1}^m \left( \frac{n-1}{n} \right)^{i-1} = \sum_{i=0}^{m-1} \left( \frac{n-1}{n} \right)^i$
This is sum to $m$ terms of a geometric series, which is straightforward:
$\hspace{2.3cm} = \frac{1- \left( \frac{n-1}{n} \right)^m}{1-\frac{n-1}{n}}=n\left[1- \left( \frac{n-1}{n} \right)^m\right]$
Check: at n=100, m=50 this gives $\approx$ 39.4994, while simulation gives:
> mean(replicate(10000,length(unique(sample(1:100,50,replace=TRUE)))))
[1] 39.4938

so that looks okay. 
The expected fraction is then $\frac{1}{n}$th of that, $1- \left( \frac{n-1}{n} \right)^m$.
Note that if $n$ is large, $(1-\frac{1}{n})^n\approx e^{-1}$, so if $m$ is some value that's at least a large fraction of $n$, $(1-\frac{1}{n})^m\approx e^{-\frac{m}{n}}$, so we get that the expected number is approximately $n (1- e^{-\frac{m}{n}})$.
Let's try that approximation on the above example where $m=50$ and $n=100$: $100 (1-e^{-\frac{50}{100}})=100(1-e^{-\frac{1}{2}})\approx 39.347$, which is fairly close to the exact answer - for a given $m/n$ it improves with larger $n$.
So a quick and reasonably accurate approximation to the fraction is $(1- e^{-\frac{m}{n}})$.
Note that when $m=n$ this gives the usual "0.632" rule.
A: I would like to corroborate again the answer from @glen-b with some experimental results.
I wrote a function $p(n,m,k)$ that tells the exact probability (is not based on simulations) of getting exactly $k$ unique elements after choosing $m$ samples with replacement from a set of $n$ elements. Notice $p$ is a pdf on $k$.
For example, if choosing 600 from 600, the expected value of $k$ is close to $600*(1-e^{-1}) \approx = 379$. It's pdf is shown in blue.

Then, I used the function $p$ to compute the expected value of $k$ and plotted my results (orange) against the formula @glen-b provided (green). As expected, the outputs were exactly the same.

And here's the code. The simulation function is added as a reference. It is never used to compute $p$ or the expected $k$. The computation of $p$ is done in python 3 and is based on Dynamic Programming DP:
import numpy as np
from functools import lru_cache
import sys; sys.setrecursionlimit(5000000)

def simulation(n, m):
    ''' From n, choose m and count unique values'''
    x = np.arange(n)
    s = np.random.choice(x, n, replace=True)
    k = len(np.unique(s))
    return k

@lru_cache(None)
def p(n,m,k):
    '''Prob. of simulation(n,m) = k. Requires 1<=n and 0<=k<=m'''
    if k==0 or n==1 or k>m:
        ans = int(m==k)
    else:
        ans = p(n,m-1,k) * k/n + p(n,m-1,k-1) * (n-k+1)/n
    return ans

def expected_k(n):
    '''Expected output of simulation(n,n) / n. DP version'''
    K = np.arange(n+1)
    P = np.array([p(n,n,k) for k in K])
    return np.multiply(K,P).sum()/n

def glen_b_answer(n):
    '''Expected output of simulation(n,n) / n. Closed formula'''
    return 1 - (1-1/n)**n

