# Number of distinct bootstrap samples

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?

• The quotation is already a remarkably simple explanation. I suspect that if you work this out with a small example--try $n=2$ or $n=3$ to start with--it will all become clear.
– whuber
Jul 11, 2014 at 19:57
• @whuber Yes, it should be, but I must be missing something. I understand why there are $n-1$ bars but why are there $2n-1$ possible positions? Jul 11, 2014 at 19:58
• Try it with $n=2$, where there will be $1$ bar and $3$ positions. Write down all three bootstrap samples, draw the diagrams for each as suggested by the quotation, and stare at them a second.
– whuber
Jul 11, 2014 at 19:59
• Still doesn't click. The $n=2$ case makes me want to write ${n+1 \choose n-1}$ which is correct for $n=2$ but not generally... Jul 11, 2014 at 20:09
• You can find a proof in the following link: rpubs.com/riazakhan94/bootstrap_distinct_sample Nov 1, 2021 at 20:07

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}$.

• Got it, thank you for your answer. The part that hadn't clicked before was #[elements being sampled] + #[bars] = n + n - 1 = 2n - 1, so that we can think of 2n-1 locations, of which we select n-1 for bars (or, equivalently, n for elements). Jul 11, 2014 at 21:13
• I had originally pictured just n+1 bar locations (which could be chosen multiple times), instead of seeing the 2n-1 locations (which can only be chosen once)... Jul 11, 2014 at 21:41

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.