Amount of Possible Bootstrap Samples I know that the total possible amount of distinct bootstrap resamples of size $n$ is $\binom{2n-1}{n-1}$. Is there any way to prove or justify this?
 A: A standard technique is the "stars and bars" construction.
By "distinct bootstrap resample" what you mean is a sequence of $N$ elements of a set of size $N$ without paying attention to their order.  Enumerate this set as $\{x_1, x_2, \ldots, x_N\}.$  Corresponding to any such sequence is the unique ordered sequence in which all of the $x_1$ in the bootstrap sample (if any) precede all the $x_2$ in the sample, which precede all the $x_3$ in the sample, etc.  This sequence, in turn, is determined by the counts $n_j$ of each $x_j.$
Draw a diagram of this sequence by placing $n_1$ stars * (representing the $n_1$ copies of $x_1$ in the sample) followed by a bar | to their right, then $n_2$ stars (representing the $n_2$ copies of $x_2$ in the sample) followed by another bar, and so on, until placing the last $n_N$ stars (but not followed by any bar).
For instance, in a set of $N=5$ elements suppose the bootstrap sample is $(x_1,x_5,x_3,x_4,x_3).$  Its ordered version is $(x_1,x_3,x_3,x_4,x_5),$ for which the counts are $(n_i) = (1,0,2,1,1).$  Its stars-and-bars diagram therefore is

* | | * * | * | *

Clearly such a diagram always has $N$ stars (because the bootstrap sample has $N$ elements) and $N-1$ bars (because they separate $N$ groups of stars).  Numbering the $N+N-1$ symbols left to right as $1,2,\ldots, 2N-1,$ note that the bars in this example have the numbers $\{2,3,6,8\}\subset\{1,2,\ldots,9\}.$
Conversely, corresponding to any diagram of $N$ stars and $N-1$ bars and an enumeration of $N$ observations we can recover the bootstrap sample.  E.g., the diagram

| | | * * * | | * * | * * * |

with $N=8$ stars and $7$ bars corresponds to the (sorted) bootstrap sample $(x_4,x_4,x_4,\,x_6,x_6,\,x_7,x_7,x_7)$ of an eight-element set.  The bars appear at positions $\{1,2,3,7,8,11,15\}\subset\{1,2,\ldots,15\}.$
To count the distinct bootstrap samples, then, it suffices to count the distinct stars and bars diagrams.  But each such diagram corresponds to an $N-1$-element subset of $N+N-1=2N-1$ positions: namely, the positions in which the bars are located.  By definition, this count is the binomial coefficient $\binom{2N-1}{N-1},$ QED.

Application
There are very efficient methods to sample without replacement and to return that result in order.  Thus, you can create bootstrap samples very efficiently with stars and bars.
To illustrate, here is an R implementation.  Given a dataset x, it generates an array, samples, whose columns represent all possible bootstrap resamples of x in terms of the positions of the bars.  (This makes it impractical to apply to real problems, where $\binom{2N-1}{N-1}$ is so large that samples cannot be stored or even computed in reasonable time.)  Because the relative chance of a resample with counts $(n_i)$ is $1/\prod (n_i!),$ columns cannot be selected uniformly from this array: the draws must be weighted by these relative chances.  A caller-specified number N of resamples is returned in an array, one column per resample.
sample.boot <- function(N=1, x) {
  n <- length(x)
  samples <- combn(2*n-1, n-1)                         # Columns represent possible bootstrap samples
  counts <- apply(rbind(0, samples, 2*n), 2, diff) - 1 # Counts the stars between the bars
  p <- exp(-colSums(lfactorial(counts)))               # Relative chances of the samples
  p <- p / sum(p)
  j <- sample.int(ncol(samples), N, replace=TRUE, prob=p)
  apply(counts[, j, drop=FALSE], 2, function(i) rep(x, i))  # Replicates each `x[i]` `n.i[i]` times
}

E.g., the commands
X <- sample.boot(1e5, c("a", "b", "c"))
table(apply(X, 2, paste0, collapse=""))

produce the output

  aaa   aab   aac   abb   abc   acc   bbb   bbc   bcc   ccc 
 3655 11171 11127 11031 22145 11224  3725 11148 11105  3669


The first line is the ordered bootstrap resample and beneath it are the counts of how many times each resample appeared among $10^5$ draws.  For instance, the chances of aaa, bbb, and ccc are all $1/3^3,$ for expected frequencies of $10^5/3^3 \approx 3704.$  The actual frequencies in this experiment were $3655,$ $3725,$ and $3669,$ differing from their expectations by small amounts attributable to the randomness of the drawing.

References

*

*Richard Stanley, Enumerative Combinatorics (Volume I), Second Edition.  Available at http://www-math.mit.edu/~rstan/ec/.


*Almost any resource on mathematical problem solving at an elementary level ("elementary" does not mean "easy" or "unsophisticated"!).  See https://brilliant.org/wiki/integer-equations-star-and-bars/ for instance.
