Chance that bootstrap sample is exactly the same as the original sample Just want to check some reasoning.
If my original sample is of size $n$ and I bootstrap it, then my thought process is as follows:
$\frac{1}{n}$ is the chance of any observation drawn from the original sample. To ensure the next draw is not the previously sampled observation, we restrict the sample size to $n-1$. Thus, we get this pattern:
$$
\frac{1}{n} \cdot \frac{1}{n-1} \cdot \frac{1}{n-2} \cdots \frac{1}{n-(n-1)} = \frac{1}{n!}.
$$
Is this correct? I stumble on why it can't be $(\frac{1}{n})^n$ instead.
 A: Note that at each observation position ($i=1, 2, ..., n$) we can choose any of the $n$ observations, so there are $n^n$ possible resamples (keeping the order in which they are drawn) of which $n!$ are the "same sample" (i.e. contain all $n$ original observations with no repeats; this accounts for all the ways of ordering the sample we started with).
For example, with three observations, a,b and c, you have 27 possible samples:
aaa aab aac aba abb abc aca acb acc 
baa bab bac bba bbb bbc bca bcb bcc 
caa cab cac cba cbb cbc cca ccb ccc 

Six of those contain one each of a, b and c.
So $n!/n^n$ is the probability of getting the original sample back.
Aside - a quick approximation of the probability:
Consider that:
$${\displaystyle {\sqrt {2\pi }}\ n^{n+{\frac {1}{2}}}e^{-n}\leq n!\leq e\ n^{n+{\frac {1}{2}}}e^{-n}}$$
so 
$${\displaystyle {\sqrt {2\pi }}\ n^{{\frac {1}{2}}}e^{-n}\leq n!/n^n \leq e\ n^{{\frac {1}{2}}}e^{-n}}$$
With the lower bound being the usual one given for the Stirling approximation (which has low relative error for large $n$).
[Gosper has suggested using $n! \approx \sqrt{(2n+\frac13)\,\pi}n^ne^{-n}$ which would yield the approximation $\sqrt{(2n+\frac13)\pi}\,e^{-n}$ for this probability, which works reasonably well down to $n=3$, or even down to $n=1$ depending on how stringent your criteria are.]

(Response to comment:) The probability of not getting a particular observation in a given resample is $(1-\frac{1}{n})^n$ which for large $n$ is approximately $e^{-1}$.
For details see
Why on average does each bootstrap sample contain roughly two thirds of observations?
