PDA

View Full Version : number theory



ratm
05-01-2007, 12:29 PM
A) How many ways can you express a nonnegative integer n as a sum of r nonnegative integers? The order matters for the sum.

n= i1 + i2 + i3 +...+ ir


B) If you express a positive integer m as a sum of r positive integer, then how may ways?

Count Iblis
05-01-2007, 06:03 PM
A) How many ways can you express a nonnegative integer n as a sum of r nonnegative integers? The order matters for the sum.

n= i1 + i2 + i3 +...+ ir


B) If you express a positive integer m as a sum of r positive integer, then how may ways?

Imagine that you have r boxes that contain zero or more apples. You have n apples in total. How many ways are there to distribute the n apples over the n boxes? You can indicate a particular distribution as follows:

ooo|oo|oooo|o||oo|...

The o's are apples the |'s are the boundaries between boxes. We don't need to indicate a "|" at the extreme left and extreme right. All distinct patterns of the o's and |'s correspond to different ways of distributing apples into the boxes. There are n o's and r-1 |'s, so there are:

\L{n+r-1\choose n}

solutions.

pka
05-01-2007, 06:42 PM
PKA
I'd really appreciate it if you could give a look to my other question titled
"Number Theory". It is from a Discrete Math class not number theory, but my professor says this section is a precursor. This problem comes from a section of Primes Divisors and Integers.
I had already looked and I do not think that it is a clear question. It certainly has nothing to do with prime divisors.

I am not sure that Count’s reading is correct. The part about order confuses to issue.
Say a+b+c+d+e=8 then according to his reading here are two solutions: a=2, b=3, c=0, d=3 & e=0; a=0, b=2,c=3,d=0, & e=3. If both of those are to be counted then Count is correct. And the answer to part b is: \L \left( {\begin{array}{c}
{n - 1} \\
{n - r} \\
\end{array}} \right).

However, there is a well know problem about the number of ‘partitions’ of an integer. It seems to me that this question may be about that.

Do you know the correct reading.