1
$\begingroup$

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.

1 Answers 1

1

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.

  • 0
    @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.2012-12-12