Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.