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 $\displaystyle x_1+x_2+\cdots+x_n=m $ is so easy and easily derived.

It is $\displaystyle \binom{m+n-1}{m}$.

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 $\displaystyle S=\{1,2,\cdots,n\}$ and the set of r-combinations of the set $\displaystyle T=\{1,2,\cdots,n+r-1\}$

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