The number of ways to distribute $r$ $identical$ $objects$ into $n$ $distinct$ $boxes$ with at least $r_i$ objects in the $i^{th}$ box is:


For example, suppose I had 12 identical objects in 4 distinct boxes, and with at least 1 object in $n$ boxes (each one).

Then I get:


How can I prove the general formula listed above?

  • $\begingroup$ Load the required items, distribute the rest with stars and bars. $\endgroup$ – Joffan Dec 11 '16 at 4:21
  • $\begingroup$ I need to prove it, I'm not sure reasoning with logic would work. What would be a more mathematical approach? $\endgroup$ – K Split X Dec 11 '16 at 4:23
  • $\begingroup$ Obviously that was just a sketch, but some degree of logical reasoning is generally required to hold the mathematics together. $\endgroup$ – Joffan Dec 11 '16 at 4:40

Let the $i^{th}$ box contain $x_{i}$ objects. Then the following holds: $$x_1 + x_2 + x_3 + ..... + x_n = r$$ Now due to the constraint mentioned $x_i \ge r_i$. So, do the following substitution: $$x_i = x_i^{'} + r_i$$ Hence all $x_i^{'} \ge 0$, i.e. they are all non-negative.

Now, the equation becomes, $$(x_1^{'} + r_1) + (x_2^{'}+r_2) + ..... +(x_n^{'}+r_n) = r \implies$$ $$x_1^{'}+x_2^{'}+x_3^{'}+.....+x_n^{'} = r - (r_1+r_2+r_3+.....+r_n)$$

Now since all $x_i^{'}$ are non-negative, the Multinomial Theorem can be used to calculate the non-negative solutions of the above mentioned equation(which are in-turn equal to the solutions of the original equation before substitution).
And after using Multinomial theorem, you get the number of ways as $\binom{(r-r_1-r_2-...-r_n)+n-1}{n-1}$.


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.