2
$\begingroup$
  • Question

    In how many ways can at most $n$ identical balls be distributed into $r$ urns so that the $i$th urn contains at least $m_i$ balls, for each $i=1,...,r$?

    Assume that $n\geq \sum_{i= 1}^r m_i$


  • My Approach

    $$ x_1 + x_2 + \cdot\cdot\cdot + x_r = S$$

    $$\sum_{i= 1}^r m_i \leq S \leq n$$

    $$x_i \geq m_i$$

    Let

    $$y_i = x_i - m_i$$

    then $$y_1+ y_2 + \cdot\cdot\cdot + y_r = S -\sum_{i= 1}^r m_i$$

    Now I will proceed to find the number of non-negative integer-valued vectors $(y_1, y_2,...,y_r)$ such that $y_1+ y_2 + \cdot\cdot\cdot + y_r = S -\sum_{i= 1}^r m_i$ for every integer $S$ in the range of $\{\sum_{i= 1}^r m_i\quad,\quad n\}$ which is equal to $$\sum\limits_{S = \sum_{i= 1}^r m_i}^n {S - \sum_{i= 1}^r m_i + r -1\choose r-1}$$


Please have a look at my solution and give me any hints/suggestions you might have.

$\endgroup$
  • $\begingroup$ What is your question actually? $\endgroup$ – user 170039 Oct 1 '14 at 13:22
  • $\begingroup$ There is Question, My Approach, and then Please have a look at my solution and give me any hints/suggestions you might have.. What do you mean? $\endgroup$ – Kermit the Hermit Oct 1 '14 at 13:24
  • $\begingroup$ I mean what question do you want the MSE to answer? Or is it that you want to verify your solution? $\endgroup$ – user 170039 Oct 1 '14 at 13:27
  • $\begingroup$ Substitute $x_i = m_i + x_i'$ where $x_i' \ge 0$. Now subtract $m_1, m_2, \dots , m_i$ from both sides of the linear diophantine equation you have written. Finally, use stars and bars as usual. $\endgroup$ – Yiyuan Lee Oct 1 '14 at 13:28
4
$\begingroup$

You really seem to have the right idea, defining $y_i=x_i-m_i$, which basically says "If I put $x_i$ balls into urn $i$, this includes $m_i$ obligatory balls and then $y_i$ more that I can choose." This reduces you to solving:

$$x_1+x_2+\dots+x_r=(y_1+m_1)+(y_2+m_2)+\dots+(y_r+m_r)=n$$

which you note is the same as:

$$y_1+y_2+\dots+y_r=n-\sum_{i=1}^r m_i.$$

My question to you is: What is $S$? How is $S$ different from $n$? Unless I'm misreading this problem, $S$ seems to be extraneous. If $S$ is the number of balls you are distributing, the question seems to indicate that $S=n$ (not just $S\le n$).

So if you'll allow us to say $M=\sum m_i$, then you are correct in your reformulation of the problem, you are basically just distributing $n-M$ balls into $r$ urns, which is:

$$\binom{n-M+r-1}{r-1}.$$

That's the last term of your summation. You don't need to sum over values of this "$S$" because you need to distribute all $n$ of the balls. (If you had such a thing, it would be like counting ways of partially distributing the balls, which the question does not seem to indicate.)

You seem to know where the binomial formula for counting these tuples comes from, but for others reading, this formula is determined as explained here.

We basically reduced the problem "distributing $n$ balls into $r$ urns with restriction $m_i$ on each urn" to "distributing $n-M$ balls into $r$ urns" by translating solutions from one to the other. You can think of it physically as starting out by putting all of the $m_i$ balls into each urn as required -- you have $n-M$ left over to distribute freely, and you can use what you already know to count how to do that.

A simpler version of this problem might be "how many ways can you give your two children \$5 allowance (in whole dollar amounts) if each child needs at least \$1?" Rather than count some complicated configuration, you can really just think of this \$1 each as already handed out to them and then solve the easier problem "how many ways can you give your two children \$3 allowance?" (In this case, the answer is 4 ways.)

I am assuming from context (and from your use of the formula) that the urns are distinguishable (they are enumerated and each has a particular value of $m_i$, so philosophically -- and practically speaking, were you to attempt this exercise -- that makes the most sense).

$\endgroup$
  • $\begingroup$ You just sparked something in me. For some reason I was thinking that you don't have to distribute all $n$ balls. Thus leading to $\sum_{i=1}^r m_i\leq x_1 + x_2 + ... + x_r \leq n$. $\endgroup$ – Kermit the Hermit Oct 1 '14 at 13:45
  • $\begingroup$ If you are are allowed to use fewer than $n$ balls total (i.e. to just use $S$ balls and throw away the $n-S$ left over), the answer is just the sum (similar to what you have): $\sum_{S=M}^n\binom{S-M+r-1}{r-1}$. $\endgroup$ – Kellen Myers Oct 1 '14 at 14:17
  • $\begingroup$ What is that $M$? Is that $\sum_{i=1}^r m_i$ ? $\endgroup$ – Kermit the Hermit Oct 1 '14 at 14:29
  • $\begingroup$ Yes, it's shorthand. I think it's defined somewhere in the middle of my answer. $\endgroup$ – Kellen Myers Oct 1 '14 at 14:33
  • $\begingroup$ Yes indeed, I missed that. I should pay more attention when reading it would seem. So taken in to consideration the way I interpreted the question, my solution would be correct? $\endgroup$ – Kermit the Hermit Oct 1 '14 at 14:37

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.