# Wasserman's AoS, Chapter 8, Question 5

We show here that the number of possible bootstrap samples $$X_1^*, \dotsc, X_n^*$$ is

${2n - 1 \choose n - 1}.$

given a sample $$X_1, \dotsc, X_n$$.

In fact, we prove the more general result that the number of ways of choosing a sample (with replacement) of size k from n objects is

${n + k - 1 \choose n - 1}.$

## Wrong Solution

It is tempting to answer that there are $$n^n$$ possibilities with the reasoning that there are n free choices for n balls. However, this overcounts the possibilities, which can be verified by hand in the simple case where $$n=k=2$$.

## Correct Solution

The proof actually counts the number of ways to write down a solution using a certain notation called stars and bars. Consider each of our observations, $$X_i$$, as a bucket and each choice as a ball that we put into a bucket. By drawing the k balls in a row, we can show which bucket they fall into by separating the balls with a line. For example, for $$n=4$$ and $$k=3$$, the choice $$X_3, X_4, X_4$$ would be written

||*|**

Similarly, we can write all solutions for $$n=2, k=3$$ as

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

The crucial point to note is that we always use $$n + k - 1$$ symbols for a solution: $$n-1$$ bars and $$k$$ balls. Any ordering of these symbols is a solution so we just need to figure out how many orderings there are. The positions of the bars completely determine the positions of the stars. There are $$n + k - 1$$ positions in total and we choose $$n-1$$ of these to be bars, so there are

${n + k - 1 \choose n - 1}$

possible solutions.

## Example

Here are all 10 possibilities for $$n=k=3$$.

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