Number of ways of choosing $m$ objects with replacement from $n$ objects

There is a set of $n$ distinct objects. How many possible multisets can we get when choosing $m$ objects with replacement? Note that the elements in a set are unordered and distinct, and the elements in a multiset may not be distinct. It is an abstract form of an example I encountered. My guess on the answer based on generalization from the example is ${{n+m-1}\choose{m}}$. It is something I vaguely remember I learned in high school, but I fail to recall how the answer is achieved.

By the way, the number of ways of chooisng $m$ objects without replacement from $n$ objects is ${{n}\choose{m}}$. Isn't it?

Any sources for reviewing the combinatorial basics? Thanks!

Solution 1:

This is often called the stars and bars problem. Yes: if you have $n$ distinct element and you want to count the number of possible selections of $m$ elements with repetitions allowed, the total is $\binom{n+m-1}{m}$.

(Yes, for combinations without replacement, the formula is $\binom{n}{m}=\frac{n!}{m!(n-m)!}$.)

I think of it as the number of distinct rolls one can make with $m$ dice, each with $n$ sides, because that is the setting in which I first learned it.

Here are two proofs of the formula for combinations with repetitions. They are essentially the same argument, just differ in the way it is presented. See also the Wikipedia page on "stars and bars".

1. Let us number our objects $1,2,\ldots,n$. Any selection of $m$ elements from these $n$ possibilities with repetition can be described as an $m$-tuple where the entries are non-decreasing: $(a_1,a_2,\ldots,a_m)$, with $1\leq a_1\leq a_2\leq\cdots\leq a_m\leq n$. This expression is unique.

   Now consider the tuple $(b_1,\ldots,b_m)$ obtained from $(a_1,\ldots,a_m)$ by letting $$(b_1,\ldots,b_m) = (a_1,a_2+1,a_3+2,\ldots,a_m+(m-1)).$$ Notice that $1\leq b_1\lt b_2\lt\cdots\lt b_n\leq n+m-1$; moreover, distinct $a$-tuples correspond to distinct $b$-tuples; and, more importantly, every $m$-tuple $(c_1,\ldots,c_m)$ with $1\leq c_1\lt c_2\lt\cdots\lt c_m\leq n+m-1$ corresponds to an $a$-tuple, namely, $(c_1,c_2-1,\ldots,c_m-m+1)$ (which will satisfy $1\leq c_1\leq c_2-1\leq\cdots\leq c_m-m+1\leq n$).

   Thus, counting $a$-tuples (that is, combinations with repetitions from $\{1,\ldots,n\}$) is equivalent to counting $b$-tuples; the advantage is that to count $b$-tuples we just need to count the number of possible $m$-tuples chosen from $\{1,2,\ldots,n+m-1\}$ without replacement. This is the basic formula $\binom{n+m-1}{m}$. Thus, the number of possible combinations with repetitions of $m$ elements chosen from $n$ possibilities is $$\binom{n+m-1}{m}.$$

2. Consider the set $\{1,\ldots,n\}$. Add in $m-1$ new symbols, $r_1,\ldots,r_{m-1}$. Think of $r_i$ as "repeat the $i$th symbol."

   Now choose without repetition an $m$-tuple from $\{1,\ldots,n,r_1,\ldots,r_{m-1}\}$. Write it out in the order that has every $r$ larger than every number, the numbers ordered in their usual way, and the $r$s ordered by their indices. For example, you might get $2,3,r_1,r_3,r_4$. This will correspond to the $m$-tuple-with-repetitions obtains by replacing $r_i$ with whatever is in the $i$th position, hence here we get $$2, 3, 2, 2, 2$$ You'll want to convince yourself here as well that every $m$-tuple-with-repetitions from $\{1,2,\ldots,n\}$ corresponds to a single $m$-tuple-without-repetitions from $\{1,2,\ldots,n,r_1,\ldots,r_{m-1}\}$ and vice-versa, so that the number of combinations-with-repetitions from $\{1,2,\ldots,n\}$ is equal to the number of combinations-without-repetitions from $\{1,2,\ldots,n,r_1,\ldots,r_{m-1}\}$. There are $n+m-1$ objects in the latter set, so we again get $$\binom{n+m-1}{m}.$$