AHi,
I have a small mathematical problem...
Here is the task:
N boxes are given. I have M stones.
In how many different ways I can put those M stones in the N boxes.
Or the same task a little changed:
N boxes are given. I have m candies and k chocolates.
In how many different ways I can put the M candies and K chocolates in the N boxes.
Is there any mathematical formula???
first task:
How many stones can be placed in one box?
if the answer is 1 then formula is: N! / ( M! * ( N-M )! );
if the answer is > 1 then: N^M
For every stone you have N choices you can make (boxes to put it in), therefore the total way of putting M stones in N boxes is N^M.
In the second task you have exactly the same situtation but with two "kinds of stones", so we just multiply the answers for individual subproblems and get the total of N^M * N^K or N^(M + K) ways.
Well all stones can be in one box...
One box can hold unlimited number of stones :)
Thanks for the really fast answer :D.
Now i go to implement this.
Hm.... If N=2 and M=2. Aren't there only 3 ways:
2 0
1 1
0 2
???
EDIT: My task clarification wasn't good. :S
I think i know for what this formula N^M is... but this isn't a solution for my problem....
EDIT2: The sample test should clarify what i need :)
I guess the formula should be
(M+N-1)! / ( M! * (N-1)! ) where 0! = 1
Say, you separate two boxes with a wall where walls are denoted by '0' and stones are denoted by '1'.
Say, we have 2 boxes and 2 stones
101
110
011
All possibilites are these.
We may generalize that we'll need N-1 walls for N boxes.
This can be reduced to the problem, with N-1 '0' and M '1' , how many different numbers can I write?
The answer is (M+N-1)! / ( M!* (N-1)! )
Well your formula is very nice...
But I have a another problem now...
Let N = 13, M = 13...
Then (M+N-1)! = 15511210043330985984000000
And that can't fit long long :S
Is there any other formula?? Or do I need to implement BigDigits ???
I guess you need to implement BigInteger.I don't know, there might be some other formulas but since this one will give a correct result, other formulas' results will be same. Maybe you can try doing something like this:
Store the elements of factorials in arrays, then cancel them according to the denominator arrays.
For example for this problem;
M+N-1! = 25 24 23... 1
M! = 13 12..., so that wil cancel most of the elements of M+N-1 ! , likewise cancel the elements of N-1 ! array,
then result will be product of elements in M+N-1 ! array.
If the result will fit in long long, then you can write numerator as product of prime factors, and same for denominator, and then cancel exponents of same factors in numerator and denominator.
