Finding \( n(D,M) \) (problem 1.15) is finding the number of ways we can sum \(D\) non-negative numbers to M. This is a basic combinatorics problem with a number of interesting solution methods. I will outline three approaches that feel somewhat different and find application in solving other problems.
\[ \mathrm{Solve:} \quad x_1+x_2+...+x_D=M \]
\[ x_i \gt =0 \quad 1 \le i \le D\]
\[ x_i \gt =0 \quad 1 \le i \le D\]
Method 1: Using generating functions
Coefficient of \(x^M\) in \( \left(1+x+x^2+....\right)^D \)
=Coefficient of \(x^M\) in \( \left(1-x\right)^{-D} \)
Using -ve binomial series the coefficient is \( \left( \begin{matrix} D+M-1\\M \end{matrix} \right) \)
Method 2: Bars and Balls
Lets say we have a set of \(M\) 1’s, and a set of \(D-1\) bars. The \(D-1\) bars split the 1’s into the number of 1's representing each of the \(D x_i\)’s . So in total we have \(D+M-1\) positions out of which we select \(M\) position for 1’s and the rest are for the bars.
A following similar approach yields the wrong solution: So we have \(M\) 1’s so we can select each bar in \(M+1\) ways. The mistake here is that selecting the first and second bars in positions 1 and 2 is the same as selecting them in positions 2 and 1. We need each new bar to come to the right of the ones we have already positioned. Okay, so can't we just select the position of \(D-1\) bars from \(M+1\) positions. This gives us the solution to the problem where each \(x_i \gt 0\) because we cannot choose the same position for two bars. However, when \(x_i \ge 0\) we are allowed to choose bars from the same position between balls so we start off with a set of positions for bars and balls and then select the positions of the bars.
Method 3: Indices
Let each \(x_i\) represent the number of balls in box \(i\). The number of boxes is \(D\) and the number of balls is \(M\). Represent each solution as a non-decreasing list of box numbers. E.g. 11335 represents 2 balls in box 1, two balls in box 3 and one ball in box 5. Now create another sequence which is the indices of the balls 01234. Add the two sequences 12569. We can see that all increasing sequences can be generated with a smallest value of 1 and a largest value of \(D+M-1\). So the number of ways is again \( \left( \begin{matrix} D+M-1\\M \end{matrix} \right) \).
The extension to problem 1.16 is then fairly straightforward. We just add another variable giving us a total of \(D+1\) dimensions and solve the same problem as above. The newly added variable will take over the leftover whenever the other \(D\) variables sum to less than \(M\). So, in this case we have the number of ways as \( \left( \begin{matrix} D+M\\M \end{matrix} \right) \)
