What is the number of integer solutions to $x_1+x_2+ \cdots + x_N = M$ where $0 \leq x_i \leq C$ for $i = 1, \dots, N$? (All constants are positive integers.)

  • $\begingroup$ Is the order important or not? $\endgroup$ – Marc Bogaerts Sep 22 '14 at 10:07
  • $\begingroup$ The order is not important; all objects are identical, all containers are similar (max C capacity). The end arrangement of the objects is important; however, the containers are indexed and can be distinguished. $\endgroup$ – Alfred Hess Sep 22 '14 at 10:11
  • $\begingroup$ i.e., the variables x. $\endgroup$ – Alfred Hess Sep 22 '14 at 10:25
  • $\begingroup$ So $x_1+x_2+\ldots$ is different from $x_2+x_1+\ldots$? $\endgroup$ – Marc Bogaerts Sep 22 '14 at 11:26
  • $\begingroup$ No, they are the same. What I meant was that x1 is different from x2, and ... $\endgroup$ – Alfred Hess Sep 22 '14 at 12:05

If you're familiar with generating functions, you can get a pretty explicit answer. Here's a stab at it. Each container can be represented with the polynomial $1+x+\dots+x^C=\frac{1-x^{C+1}}{1-x}$, which is a sum of powers of $x$, one for each allowable number of objects in a container. Then, the way to represent the collection of all $n$ containers is by taking the product of these polynomials, namely $\left(\frac{1-x^{C+1}}{1-x}\right)^N$. Now the coefficient of $x^M$ in this product gives the number of ways to arrange exactly $M$ objects among the $N$ containers. In other words, the number of solutions to your equation is $$[x^M]\left(\frac{1-x^{C+1}}{1-x}\right)^N.$$ To extract this coefficient takes a bit of maneuvering. However, with the binomial theorem and some knowledge of the Taylor series of $\frac1{(1-x)^N}$, you should be able to do this and get the exact count you're looking for, as a sum of $N$ terms of products of binomial coefficients.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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