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.

Re: r-Combinations with Repetition Allowed

Quote:

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 is so easy and easily derived.

It is .

I do not understand what this question means really.

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!

Re: r-Combinations with Repetition Allowed

Quote:

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?

Re: r-Combinations with Repetition Allowed

Discrete Mathematics with Applications, 4th edition.

Re: r-Combinations with Repetition Allowed

Quote:

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 and the set of r-combinations of the set

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