When I was learning combinatorics for the first time (I was probably 16) there was this problem about distributing balls in bins (or urns) that I came across. We had to count the total number of such distributions, given certain constraints on the maximum capacities of bins. For example, assuming that each bin must have at least one ball and that there is no upper limit on their capacity, we showed that there are ways of distributing identical balls in distinct bins. Clearly, this is equal to the number of solutions of , where each must be a positive integer. Not so clearly, this is also equal to the coefficient of in .
A few days back, this problem appeared again. This time, in the context of some research problems that I am working on. I will explain what the context is in some later posts. For now, let’s stick to elementary combinatorics.
We are given bins , where for every , the bin has maximum capacity . We are going to distribute balls in these bins such that each bin gets at least one ball. But instead of counting the total number of ways of doing this, we are interested in finding distributions that minimize the product , where is the number of balls in the bin . Since the product doesn’t depend on the order, we will assume that . We will denote the minimum value of the product by .
Let us start with a small example. Say we have balls that we want to distribute in two bins and of capacities and , respectively. Then, these are the all possible distributions: . The minimum product is attained at , and hence . Before reading further, you might want to play around with some more examples to see if a pattern emerges …
So, here’s how a solution goes . Define a greedy distribution to be the one where you first place a single ball in each of the bins, and then the remaining balls are placed from left to right, moving from the bin to the bin only after you have already placed (the maximum capacity of ) balls in . We will now prove that this greedy distribution minimises the product by showing that from any given distribution , we can reach the greedy distribution by performing certain moves, such that after each such move the product remains the same or reduces. The moves that we’ll perform are of the following two types:
- Bin Swap: If there are bins and , with , such that , then swap the balls in these two bins.
- Unbalancing Move: If there are bins and , with , such that , then move a ball from the bin to the .
In the first move, the product doesn’t change. While in the second move, the product reduces, as the ratio of the new product to the old product is equal to , which is less than because .
After some thought, it should be clear that by first performing Bin Swaps, and then doing the Unbalancing Moves on any starting distribution , we can reach the greedy distribution.This shows that the greedy distribution must minimize the product. Of course, it might be that it is not the unique distribution that minimises the product.
We can now deduce the following facts about the function that will be useful later.
- , where is the remainder when you divide by , and is the quotient.