# Combinatorics with repetitons

I have read that in combinations with repetitions, the number of ways of selecting r objects out of n is: $$\binom{n+r-1}{r}$$ I have also read that this is the number of positive solutions for the linear equation of the form: $$x_1 + x_2 + x_3 + x_4 +\cdots + x_r = n\qquad(E)$$

We can model equation $(E)$ as a case where we fill up $r$ boxes with $n$ digits from $0$ to $9$. It can be graphically represented as: $$xx\ldots x|xx\ldots x|xx\ldots x|\ldots|xx\ldots x|xx\ldots x$$ where $|$ represents a partition between two boxes (hence we have $(r-1)$ partitions for $r$ boxes).

The number of solutions of $(E)$ is the number of ways in which we can arrange these $(r-1)$ $|$'s and $n$ $x$'s. This is equal to $\frac{(n+r-1)!}{n!(r-1)!}$. This is easy because we have to arrange $(n+r-1)$ symbols where n are one type and $(r-1)$ are of another. This expression can, however, be written as $\binom{n+r-1}{r}$ .

Here is my doubt: Is this is a coincidence? If no, then what is the combinatorial argument for it? How do we interpret such questions of permutations in terms of combinations?

I really hope that I was able to convey my doubt. If no, then please tell where I need to provide more information.

-
add comment

## 1 Answer

No, it’s not coincidence. Suppose that you’re forming a multiset of $n$ objects, where the objects are of $r$ types. Take $k$ boxes and label each box with one of the types. Distributing $n$ marbles amongst these $r$ boxes is in effect choosing a multiset of $n$ elements from these $r$ types: if you put $k$ marbles in box $i$, you’re saying that there are $k$ objects of type $i$ in your multiset.

Alternatively, you can think of the variables $x_1,\dots,x_r$ in your equation as specifying the numbers of objects of types $1,2,\dots,r$, respectively, in your $n$-element multiset.

These really are just three manifestations of the same underlying combinatorial situation.

-
Thanks for the answer. Multiset really elucidated the concept. Also , the thought that I presented in my questions ( about total number of permutations when we have many objects but those can be divided into two types ) can be used to understand this concept,yes? –  kusur Dec 12 '12 at 9:09
@Kunal: You mean the idea of distinguishing between the marbles (x) and the spaces between the boxes (|)? Yes, that’s the easiest way that I know to derive the formula. –  Brian M. Scott Dec 12 '12 at 9:13
add comment