Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose I have 3 non-negative integers and I have to achieve 4 by adding these numbers .There are 15 ways to get 4 by adding 3 non-negative integers . They are

1.      0 0 4
2.      0 1 3
3.      0 2 2
4.      0 3 1
5.      0 4 0
6.      1 0 3
7.   1 1 2
8.   1 2 1
9.   1 3 0
10.  2 0 2
11.  2 1 1
12.  2 2 0
13.  3 0 1
14.  3 1 0
15.  4 0 0 

I want to know the number of ways to get n by adding k non-negative integers . n and k can be very big . (1 ≤ k ≤ 10^6) , (0

share|improve this question
1  
Classic stars and bars problem - en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) –  gt6989b Feb 26 '13 at 20:48

1 Answer 1

up vote 1 down vote accepted

This is classic stars and bars problem - http://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics).

You have a string of 4 stars and 2 bars (to split it into 3 pieces, one for each variable), there are a total of $\binom{4+2}{2} = \binom{4+2}{4} = \frac{6!}{4!2!} = 15$ such strings, each corresponding to a unique assignment, so there is 15 assignments...

share|improve this answer
    
What is meant by "2 bars" ? Is it "k-1" ?? –  Way to infinity Feb 26 '13 at 22:37
    
@SultanAhmedSagor Yes, in general case, you are looking for ways to get $n=4$ using $k=3$ integers, and the result is $n$ starts, $k-1$ bars, to $\binom{n+k-1}{n} = \binom{n+k-1}{k-1}$. –  gt6989b Feb 27 '13 at 13:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.