# Math Help - r-Combinations with Repetition Allowed

1. ## r-Combinations with Repetition Allowed

Another way to count the number of nonnegative integral solutions to an equation of the form x1+x2+...+xn=m is to reduce the problem to one of finding the number of n-tuples (y1,y2,...,yn) with 0<=y1<=y2<=...<=yn<=m. The reduction results from letting yi=x1+x2+...+xi for each i=1,2,...,n. Use this approach to derive a general formula for the number of nonnegative integral solutions to x1+x2+...+xn=m.

I'm not even sure where to start with this problem. I would appreciate any help.

2. ## Re: r-Combinations with Repetition Allowed

Originally Posted by lovesmath
Another way to count the number of nonnegative integral solutions to an equation of the form x1+x2+...+xn=m is to reduce the problem to one of finding the number of n-tuples (y1,y2,...,yn) with 0<=y1<=y2<=...<=yn<=m. The reduction results from letting yi=x1+x2+...+xi for each i=1,2,...,n. Use this approach to derive a general formula for the number of nonnegative integral solutions to x1+x2+...+xn=m.
I'm not even sure where to start with this problem. I would appreciate any help.
Where did you get this problem? It is really puzzling.
The solution to “counting the number of nonnegative integral solutions to an equation of the form $x_1+x_2+\cdots+x_n=m$ is so easy and easily derived.
It is $\binom{m+n-1}{m}$.

I do not understand what this question means really.

3. ## Re: r-Combinations with Repetition Allowed

It is from a Discrete Math textbook. I am familiar with the formula (m + n - 1, m); I just wasn't sure how to "derive" it. Thanks for your help!

4. ## Re: r-Combinations with Repetition Allowed

Originally Posted by lovesmath
It is from a Discrete Math textbook. I am familiar with the formula (m + n - 1, m); I just wasn't sure how to "derive" it. Thanks for your help!
Which textbook?

5. ## Re: r-Combinations with Repetition Allowed

Discrete Mathematics with Applications, 4th edition.

6. ## Re: r-Combinations with Repetition Allowed

Originally Posted by lovesmath
Discrete Mathematics with Applications, 4th edition.
I no longer have Ken Rosen's Fourth edition. But I see in the Fifth edition he has changed the question.
He wants you to show that there is a one-to-one correspondence between the set of r-combinations of the set $S=\{1,2,\cdots,n\}$ and the set of r-combinations of the set $T=\{1,2,\cdots,n+r-1\}$

I hope that helps you. But I will not be a part of reinventing the wheel.