# In how many ways can I distinguishable balls be thrown to B bins with capacity C such that no bin exceeds its capacity

Assume there are $$B$$ bins and $$I$$ balls. Each bin has the same capacity $$C$$. Bins with more than $$C$$ balls are not allowed. Also, the balls are equiprobable but distinguishable, i.e., the ball $$i_1$$ being in the bin $$b_1$$ is different from the ball $$i_2$$ being in the bin $$b_1$$ (although the configurations may have the same probability).

After the i-th attempt, how many configurations are possible such that none of the B bins have more than C balls?

An attempt is defined as "throw a ball into a bin". After the first attempt 1 bin has exactly 1 ball, before the first attempt all the bins are empty.

For example, imagine $$B=2$$, $$C=2$$, $$I=4$$. After the first attempt there are $$2$$ possible configurations. After the second attempt there are $$4$$. After the third there are $$6$$ (one bin with 1 ball the other with 2). After the forth there are also $$6$$ (both bins with 2 balls).

The invalid configurations from the previous iterations must be removed when computing the next one. If the capacity restriction is removed, then, after the i-th attempt there whould be $$B^i$$ possible configurations.

I already checked the link below, but I think they consider the balls to be indistinguishable.

http://www.mathpages.com/home/kmath337.htm

EDIT 1:

I don't know it this is correct, but here goes a draft of the answer:

With capacity $$C$$ there are a maximum and a minimum number of filled bins, i.e., bins at full capacity, at i-th attempt.

Let us define $$min_c(B,C,I)$$, i.e. minimum filled bins, and $$max_c(B,C,I)$$, i.e., maximum filled bins as follows:

$$max_c(B,C,I) = \left\lfloor \frac{I}{C} \right\rfloor$$ $$min_c(B,C,I) = \max(0, I-B(C-1))$$

(to find the minimum think of fill the bins with $$C-1$$ balls, until $$B(C-1)$$ balls are thrown, from there, every consequent attempt will fill a bin)

$$\sum_{x=min_c(B,C,I)}^{max_c(B,C,I)} \binom{B}{x} \prod_{y=0}^{x-1} \binom{I-yC}{C} \times ...$$

The amount of configurations where bins are filled with capacity $$C$$ is given in the expression above. Now, the given number of configurations, must be multiplied by the configurations of the remaining $$I-xC$$ balls in the remaining $$B-x$$ bins, the maximum allowed capacity for the remaining configurations is now $$C-1$$.

$$\sum_{x=min_c(B,C,I)}^{max_c(B,C,I)} \binom{B}{x} \prod_{y=0}^{x-1} \binom{I-yC}{C} \times \sum_{x'=min_c(B-x,C-1,I-xC)}^{max_c(B-x,C-1,I-xC)} \binom{B-x}{x'} \prod_{y'=0}^{x'-1} \binom{I-xC-y'(C-1)}{C-1} \times ...$$

You keep repeating that pattern until C is 1.

If this is correct. I'd like to find a closed form for this.

EDIT 2:

I think that the previous formula can be written as:

$$f(B,C,I)=\begin{cases} 1 & \text{, if } B=0 \lor I=0 \\ \displaystyle \sum_{x=min_c(B,C,I)}^{max_c(B,C,I)} \binom{B}{x} \prod_{y=0}^{x-1} \binom{I-yC}{C} f(B-x,C-1,I-xC) & \text{, otherwise } \\ \end{cases}$$

If that is right, is there a non-recursive form?

• You didn't define what an "attempt" is. So you throw them one ball at a time or something? – 6005 Sep 29 '16 at 14:00
• An attempt is "throw a ball into a bin". I'll change that. – Daniel Castro Sep 29 '16 at 14:06
• After the second attempt, you could have 2-0, 0-2 or 1-1. What is the fourth configuration ? – true blue anil Sep 29 '16 at 15:00
• in the first attempt you have 1-0 or 0-1, then in the second you have 2-0, 0-2 or 1-1, or 1-1 (you can put the ball in the second bin or in the first of the previous attempt, so you get two 1-1). The balls are "distinguishable". – Daniel Castro Sep 29 '16 at 16:17