1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You didn't define what an "attempt" is. So you throw them one ball at a time or something? $\endgroup$ – 6005 Sep 29 '16 at 14:00
  • $\begingroup$ An attempt is "throw a ball into a bin". I'll change that. $\endgroup$ – Daniel Castro Sep 29 '16 at 14:06
  • $\begingroup$ After the second attempt, you could have 2-0, 0-2 or 1-1. What is the fourth configuration ? $\endgroup$ – true blue anil Sep 29 '16 at 15:00
  • $\begingroup$ 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". $\endgroup$ – Daniel Castro Sep 29 '16 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.