Number of distinct bootstrap samples

Question

For $n$ distinct observations, there are ${2n - 1 \choose n-1}$ distinct bootstrap (re)samples.

Could someone please provide a simple explanation?

I found http://statweb.stanford.edu/~susan/courses/s208/node11.html, which includes the following:

The set of all bootstrap resamples is the $n$ dimensional simplex $$C_n=\{(k_1,k_2,\ldots,k_n), \,k_i \in \mathbb{N}, \,\sum k_i=n\}$$

Here is the argument I used in class to explain how big $C_n$ is. Each component in the vector is considered to be a box, there are $n$ boxes to contain $n$ balls in all, we want to contain to count the number of ways of separating the n balls into the $n$ boxes. Put down $n-1$ separators of $\vert$ to make boxes, and $n$ balls, there will be $2n-1$ positions from which to choose the $n-1$ bars' positions, for instance our vector above corresponds to: oo||o|oo| . Thus $$\displaystyle \vert C_n \vert={{2n-1}\choose{n-1}}$$

This makes sense to me with the exception of one crucial point: why will there be "$2n - 1$ positions from which to choose the $n-1$ bars' positions"?

I tried justifying it to myself and came up with this:

I need to find a set of size $2n - 1$ of possible bar locations. At first glance there are $n+1$ locations in which the bars can be placed, but the catch is that positions can be chosen multiple times.

To be clear, using o to represent a ball as in the block-quote above: _o_o_o_o_o_ ie 5 balls means 6 slots (underscores) in which bars can live. But there can be multiple bars in one location, e.g. ||ooo||oo .

The set I came up with is $$L = \left\{0, 1, \ldots, n, s_1, \ldots, s_{n-2}\right\}$$ which has size $2n - 1$ as desired. The first $n+1$ elements are integers; the last $n-2$ elements are symbols: $s_i$ means "go to the same slot as bar $i$."

Elements of L are possible locations for the bars. The rule for placing the bars is:

1. Draw a sample $\tilde{L}$ of size $n-1$ from $L$
2. Order the elements of $\tilde{L}$ so that the integers come first (in ascending order), followed by any $s_i$, in ascending order of the $i$; note that there is necessarily at least one integer in $\tilde{L}$
3. The $j^{th}$ element of $\tilde{L}$ will tell us where to place bar $j$. If $\tilde{L}_j$ is an integer, place bar $j$ in slot number $\tilde{L}_j$; if it is an $s_i$, place bar $j$ in the same slot as bar $i$ (the sorting guarantees $i < j$)

My question is twofold: does my explanation make sense? Even if it does, it seems unnecessarily messy and complicated. Can you think of something clean and simple?

Answer 1

Let's ask the computer to generate some small examples. (The language is R.)

Take $n=5$. Begin by placing $n-1$ bars (represented as ones) randomly within $n + n-1 = 2n-1$ places; that is, by selecting an $n-1$ element subset of $\{1,2,\ldots,2n-1\}$:

n <- 5
set.seed(17)
y <- rep(0, 2*n-1)
y[sample.int(2*n-1, n-1, replace=FALSE)] <- 1
names(y) <- c("_","|")[y+1]
print(y)

The output is

_ | _ | | _ _ | _ 
0 1 0 1 1 0 0 1 0

The $n-1=4$ selected elements are shown with bars. Between them appear five boxes of sizes 1, 1, 0, 2, and 1, respectively. These counts can be easily computed:

x <- tabulate(cumsum(c(1,y)))-1
names(x) <- 1:n
print(x)

The output is

1 2 3 4 5 
1 1 0 2 1 

This tabulation means that 1 "1" was selected, 1 "2", no "3"s, 2 "4"s, and 1 "5". (To appreciate what happened, inspect the intermediate result:

cumsum(c(1,y))

  _ | _ | | _ _ | _ 
1 1 2 2 3 4 4 4 5 5 

Beginning with a 1 (which corresponds to none of the boxes or bars), the cumulative sum incremented the value every time a bar was crossed. Because there are $n-1=4$ bars, the final value is $1+(n-1)=n=5$. Thus every possible outcome in $\{1,2,\ldots,n\}$ is named at least once. The code counted the number of times each outcome was mentioned and decremented that count by one.)

We could equally well write the same information as an array of the sample values by replicating each value (in the first row) the number of times indicated (in the second row):

print(z <- unlist(mapply(rep, 1:n, x)))

The output is

[1] 1 2 4 4 5

These are the sample values, sorted for your convenience. Finally, they can be converted back to boxes and bars:

unlist(sapply(tabulate(z), function(i) c(1,rep(0, i))))[-1]

This command creates one box for each sample element and sticks a bar in front of the first box for each new element processed. After removing the initial bar, the output is what we started with (y).

Because this code goes full circle from one of the three different representations of a given sample back to itself, it shows that any one of the representations can be converted uniquely to any of the other two forms. Therefore all configurations of each of the three forms of representation are in one-to-one correspondence. In particular, the number of possible arrays z that name the sample members explicitly is the same as the number of ways of creating y, which (by definition) is $\binom{2n-1}{n-1}$.

Answer 2

Notice that we want to take $n$ elements from the original set ($n$ distinct elements sample set) with replicates allowed.

Then suppose if I denote $x_1$: number of replicates of the first element, $x_2$: number of replicates of second element,...., $x_n$: number of replicates of $n$th element. While we must take elements $n$ times, that is, we can convert this question to number of different solutions of the equation: $x_1+...+x_n = n$.

Now suppose we have $n$ indistinguishable balls and $n$ distinguishable cells, and we want to put $n$ balls into cells. The key is how many balls that each cell contains? Since there are $n$ cells thus $n - 1$ bars to separate them, the point to make each assignment of balls distinct is: how many different ways can we assign the locations of $n - 1$ bars to make each assignment different? We have $n$ balls and $n - 1$ cells thus $2n - 1$ objects and $\binom{2n-1}{n - 1}$ ways to place the bars. Thus we get the answer.