## Balls in Bins

When I was learning combinatorics for the first time (I was probably 16) there was this problem about distributing $m$ balls in $n$ 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 ${m - 1 \choose n - 1}$ ways of distributing $m$ identical balls in $n$ distinct bins. Clearly, this is equal to the number of solutions of $x_1 + \cdots + x_n = m$, where each $x_i$ must be a positive integer. Not so clearly, this is also equal to the coefficient of $t^{m-n}$ in $(1-t)^{-n}$.

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 $n$ bins $A_1, \ldots, A_n$, where for every $i$, the bin $A_i$ has maximum capacity $a_i$. We are going to distribute $m$ balls in these $n$ 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 $x_1 \cdots x_n$, where $x_i$ is the number of balls in the bin $A_i$. Since the product doesn’t depend on the order, we will assume that $a_1 \geq a_2 \cdots \geq a_n$. We will denote the minimum value of the product by $\mathfrak{m}(a_1, \ldots, a_n; m)$.

Let us start with a small example. Say we have $5$ balls that we want to distribute in two bins $A$ and $B$ of capacities $4$ and $3$, respectively. Then, these are the all possible distributions: $(4, 1), (3, 2), (2, 3)$. The minimum product is attained at  $(4, 1)$, and hence $\mathfrak{m}(4, 3; 5) = 4$.  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 [1]. Define a greedy distribution to be the one where you first place a single ball in each of the $n$ bins, and then the remaining $m-n$ balls are placed from left to right, moving from the bin $A_i$ to the bin $A_{i+1}$ only after you have already placed $a_i$ (the maximum capacity of $A_i$) balls in $A_i$. We will now prove that this greedy distribution minimises the product by showing that from any given distribution $x = (x_1, \ldots, x_n)$, 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:

1. Bin Swap: If there are bins $A_i$ and $A_j$, with $i < j$, such that $x_i < x_j$, then swap the balls in these two bins.
2. Unbalancing Move: If there are bins $A_i$ and $A_j$, with $i < j$, such that $a_i > x_i$ $\geq x_j > 1$, then move a ball from the bin $A_j$ to the $A_i$.

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 $\frac{(x_i + 1)(x_j - 1)}{x_ix_j} = \frac{x_ix_j + x_j - x_i - 1}{x_ix_j}$, which is less than $1$ because $x_j \leq x_i$.

After some thought, it should be clear that by first performing Bin Swaps, and then doing the Unbalancing Moves on any starting distribution $x$, 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 $\mathfrak{m}(a_1, \ldots, a_n; m)$ that will be useful later.

1. $\mathfrak{m}(2, \ldots, 2; 2n - k) = 2^{n-k}$.
2. $\mathfrak{m}(a, \ldots, a; m) = (r+1)a^k$, where $r$ is the remainder when you divide $m-n$ by $a - 1$, and $k$ is the quotient.