# Counting question?

• May 17th 2008, 03:38 AM
sakhr98
Counting question?
Greetings,

I have the following question in couting. It might be straight forward but I could not find a formula for the answer.

Let N and m be positive integers.

How many combinations are there of the form:

n1, n2, ..., nN such that

n1 >=0, n2>=0, ..., nN >= 0, and
n1 + n2 + n3 + ... + nN = m.

Example: N = 3, m = 4:
All combinations are given by
1) 4, 0, 0,
2) 3, 1, 0,
3) 3, 0, 1,
4) 2, 2, 0,
5) 2, 1, 1,
6) 2, 0, 1,
7) 1, 3, 0,
8) 1, 2, 1,
9) 1, 1, 2,
10) 1, 0, 3,
11) 0, 4, 0,
12) 0, 3, 1,
13) 0, 2, 2,
14) 0, 1, 3,
15) 0, 0, 4

Therefore, the number of combinations for this example is 15.

Best regards.
• May 17th 2008, 03:46 AM
Moo
Hello,

Quote:

Originally Posted by sakhr98
Greetings,

I have the following question in couting. It might be straight forward but I could not find a formula for the answer.

Let N and m be positive integers.

How many combinations are there of the form:

n1, n2, ..., nN such that

n1 >=0, n2>=0, ..., nN >= 0, and
n1 + n2 + n3 + ... + nN = m.

Example: N = 3, m = 4:
All combinations are given by
1) 4, 0, 0,
2) 3, 1, 0,
3) 3, 0, 1,
4) 2, 2, 0,
5) 2, 1, 1,
6) 2, 0, 1,
7) 1, 3, 0,
8) 1, 2, 1,
9) 1, 1, 2,
10) 1, 0, 3,
11) 0, 4, 0,
12) 0, 3, 1,
13) 0, 2, 2,
14) 0, 1, 3,
15) 0, 0, 4

Therefore, the number of combinations for this example is 15.

Best regards.

If I've understood correctly your question, the formula is :

${m \choose N+m-1}={N-1 \choose N+m-1}$

I can try to explain..
• May 17th 2008, 04:19 AM
sakhr98
Thank you for the prompt reply.

I am not sure I get your answer. For the example I put, N = 3 and m = 4, substituting in your formula results in C(2, 6) = C(4, 6).
But what is the definition of C(2,6)?

Best regards, Ashraf.
• May 17th 2008, 04:21 AM
Moo
The definition ?

$C(p,n)={p \choose n}=\frac{n!}{(n-p)!p!}$

Is it what you want ?
• May 17th 2008, 04:34 AM
sakhr98
I apologize for my hastiness. Your answer is correct except for the typo where the answer is C(N+m-1, m) = C(N+m-1, N-1).

Thank you very much.
• May 17th 2008, 04:39 AM
Moo
Quote:

Originally Posted by sakhr98
I apologize for my hastiness. Your answer is correct except for the typo where the answer is C(N+m-1, m) = C(N+m-1, N-1).

Thank you very much.

Yeah, I have real difficulties with this formula...

You're welcome
• May 18th 2008, 05:47 PM
awkward
Quote:

Originally Posted by Moo
Hello,

If I've understood correctly your question, the formula is :

${m \choose N+m-1}={N-1 \choose N+m-1}$

I can try to explain..

Ahem.

Moo, I believe the usual convention on the notation for combinations is that $\binom{n}{m}$ is the number of combinations of n objects taken m at a time.

$\binom{N+m-1}{m} = \binom{N+m-1}{N-1}$.