View Full Version : number theory

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

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.

Powered by vBulletin® Version 4.2.2 Copyright © 2014 vBulletin Solutions, Inc. All rights reserved.