[Math] $n$ Identical Balls Distributed Into $r$ Urns

combinatorics

  • 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.

Best Answer

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).

Related Question