[Python] Find the number of ways of placing m identical balls in n different boxes where each...

Given (m, n, k)
For (4, 3, 2) the answer is 6
Explanation: The first row tells that there are 2 balls in box1, 2 balls in box2 and 0 balls in box3. This is one way of distributing 4 balls. The other rows can be interpreted the same way. We can arrange 4 identical balls in 3 different boxes like below so there are 6 ways of distributing the balls.

Box 1 Box 2 Box 3
2 2 0
2 0 2
0 2 2
2 1 1
1 2 1
1 1 2

Sample Inputs and Solutions: (3, 3, 3) = 10 (6, 4, 3) = 44 (6, 4, 2) = 10 (3, 3, 2) = 7
Is there any formula for this? or is there any dynamic programming approach for this?

I tried brute force approach where i iterated through all possible permutations and eliminated the repeating permutations. I am thinking that there should exist some dynamic programming approach or mathematical formula which should give me the result.

Continue reading...