Thread: A balls and boxes problem

Hello,
I would be extremely grateful for any help with this problem:

Let be numbers such that and .

Find the number of ways we can put indistinguishable balls into distinguishable boxes, so that:
-exactly three boxes remain empty,
-two boxes contain exactly balls, and that
-each of the remaining boxes has at least balls.

*******

For example, I tried to sketch one of the possible distributions in case that and :



-the second, third and sixth boxes are empty;
-the first and fourth box contain exactly 2 balls;
-the fifth box contains three balls (which is > 2).

******

Now, how could this problem be solved for any as defined above? I know that we can find the number of partitions of a set containing n elements into k non-empty parts by Stirling numbers of the second kind, -- but in this problem, three of the parts must be empty! Should we first break this problem down into several disjoint cases where we first determine where would the empty boxes be, and then fill the remaining boxes with balls? There are, I believe, ways we can choose three of n distinguishable boxes to be empty, there then remain boxes in each case to be filled with balls. Of those boxes, 2 must contain exactly balls. We can choose those boxes in ways, and in those boxes we put balls. There now remain boxes to be filled with balls, but under the condition that there are at least balls in each of the remaining boxes...


Is this the right way to approach this problem? I'm not certain that the above argument is entirely correct, and would really appreciate some pointers in the right direction.

Many thanks!

Originally Posted by gusztav

Hello,
I would be extremely grateful for any help with this problem:

Let be numbers such that and .

Find the number of ways we can put indistinguishable balls into distinguishable boxes, so that:
-exactly three boxes remain empty,
-two boxes contain exactly balls, and that
-each of the remaining boxes has at least balls.
[snip]

PaulRS and Gustav,

I think the preceding solution over-counts some of the arrangements by looking at ways to choose 2 boxes which contain exactly k balls and then multiplying by the number of ways to arrange at least k balls in the remaining boxes. The problem is that some of those arrangements will also include 2 boxes containing exactly k balls, and those arrangements are counted more than once.

So here is an alternative approach which I think avoids that difficulty. As before, first choose the three empty boxes, which can be done in

ways. We now want to count the number of ways in which r balls can be put into n-3 boxes so that at least 2 boxes contain exactly k balls and all boxes contain at least k balls. Call this number N.

To compute N, we count the number of ways to put r balls into n-3 boxes with at least k balls in each box and then subtract the number of arrangements which violate the "at least 2 boxes with exactly k balls" constraint. The unsatisfactory arrangements can be broken into two disjoint subsets: (1) those with no box containing k balls, so all the boxes contain at least k+1 balls; and (2) those with exactly one box containing k balls, and all the other boxes containing at least k+1 balls. Modifying PaulRS’s notation slightly, let

,

the number of ways to place k balls in n boxes with no constraints. Then the number of ways to put r balls into n-3 boxes with at least k balls in each box is
.
The number of ways to put r balls into n-3 boxes with at least k+1 balls in each box is
.
The number of ways to put k balls into one box and at least k+1 balls into each of the remaining boxes is
.

So

and the answer to the original problem is
.