Probability of assigning balls into buckets, where each bucket has a certain capacity.

Question

I'll start with a specific example of what I am trying to solve:

I have eight balls to be randomly placed into four buckets. Buckets #1-3 have the capacity of 2, 2, 3 respectively, while bucket #4 has an infinite capacity. A bucket can't be filled over its capacity. A ball will not be thrown to a bucket that is already full. I would like to calculate the probability that my eight balls will completely fill buckets #1-3.

The last time I studied maths formally was in university, a good 7-10 years ago. My limited memory/understanding of combinatorics is failing me. I'm a software guy, so I wrote a basic simulator for the problem, which seems to tell me that my eight balls will fill buckets #1-3 ~18% of the time. I'd like to understand how to approach the problem mathematically.

Answer 1

The capacities of each cell make this a tricky problem. The probability of reaching a given configuration depends on the sequence of cells selected. For example, throwing balls into cells 1,1,2, in that order, has probability $(1/4)^2(1/3)$ while 1,2,1 has probability $(1/4)^3.$ So determining equally likely outcomes is difficult. Instead we can solve using a Markov chain. Let the states of the chain be the vector of number of balls in the 4 cells after any number of balls have been thrown. We start in state $(0,0,0,0)$ and throw 8 balls, one by one, taking into account the capacities. After the first ball, we are in state $(1,0,0,0), (0,1,0,0), (0,0,1,0)$ or $(0,0,0,1)$. And they each have probability $1/4$ of occurring. Similarly, we must fill in a one-step transition matrix $P$ that gives the probability of moving from any state $(i,j,k,m)$ to any other after one more ball is thrown. With 8 balls thrown the capacities are: $2,2,3,8$ and so the number of states we need to consider is $3x3x4x9=324.$

We then compute the elements of the matrix $P$ of size 324x324 (mostly $0$). This was easy in Excel. Then we compute the power $P^8.$ The non-zero probabilities in row $(0,0,0,0)$ of $P^8$ tell us the probability of being at each given state after $8$ balls are thrown.

The results show that state $(2,2,3,1)$ has probability $0.1855$ and it is the most likely to occur. There are 36 states that can occur after 8 balls are thrown.

Answer 2

If the order does matter:

$$\text{Coefficient of $x^8$ in } \\8! \underbrace{(1+x+x^2/2!)^2}_{\text{bucket 1 & 2}} \underbrace{(1+x+x^2/2!+x^3/3!)}_{\text{bucket 3}} \underbrace{(1+x+x^2/2!+\cdots\infty)}_{\text{bucket 4}}$$ $$\small\text{Coefficient of $x^8$ in } \\\small8! \underbrace{\left(\frac{x^7}{24}+\frac{7\times x^6}{24}+\frac{13\times x^5}{12}+\frac{31\times x^4}{12}+\frac{25 x^3}{6}+\frac{9\times x^2}{2}+3 x+1\right)}_{\text{bucket 1,2 & 3}} \underbrace{(1+x+x^2/2!+\cdots\infty)}_{\text{bucket 4}}$$ $$=8!\left(\frac{1}{24}.\frac{1}{1!}+\frac{7}{24}.\frac{1}{2!}+\frac{13}{12}.\frac{1}{3!}+\frac{31}{12}.\frac{1}{4!}+\frac{25}{6}.\frac{1}{5!}+\frac{9}{2}.\frac{1}{6!}+\frac{3}{1}.\frac{1}{7!}+\frac{1}{1}.\frac{1}{8!}\right)$$ $$=20857$$ For $(2,2,3,1)$ there is:$$8!\left(\frac1{2!}\right)^2\left(\frac1{3!}\right)\left(\frac1{1!}\right)=1680$$ So probability is $1680/20857\approx8.05\%$

---

Note: I have considered order inside bucket irrelevant, for e.g. if you put $1$^st ball in bucket $1$ then $2$^nd ball in bucket $1$, this is same as $2$^nd in bucket $1$ then $1$^st in bucket $1$. Also if you wish to include that order too multiply the below result in $8!$, so that both numerator and denominator's $8!$ factor cancels and you'll get the same probability of $1/36$

---

If the order doesn't matter:

$$\text{Coefficient of $x^8$ in } \underbrace{(1+x+x^2)^2}_{\text{bucket 1 & 2}} \underbrace{(1+x+x^2+x^3)}_{\text{bucket 3}} \underbrace{(1+x+x^2+\cdots\infty)}_{\text{bucket 4}}$$ $$\text{Coefficient of $x^8$ in } \underbrace{(x^7+3 x^6+6 x^5+8 x^4+8 x^3+6 x^2+3 x+1)}_{\text{bucket 1,2 & 3}} \underbrace{(1+x+x^2+\cdots\infty)}_{\text{bucket 4}}$$ $$=1+3+6+8+8+6+3+1=36$$ Numerically these correspond to: $$\begin{array}{|c|c|}\hline \text{No. of balls in bucket }(1+2+3)&\text{ways}&\text{#ways}\\\hline 0&(0,0,0)&1\\ 1&(0,0,1)\times3&3\\ 2&(0,1,1)\times3+(0,0,2)\times3&6\\ 3&(0,1,2)\times6+(0,0,3)+(1,1,1)&8\\ 4&(0,1,3)\times2+(0,2,2)\times3+(1,1,2)\times3&8\\ 5&(0,2,3)\times2+(1,2,2)\times3+(1,1,3)&6\\ 6&(1,2,3)\times2+(2,2,2)&3\\ 7&(2,2,3)&1\\\hline &**Sum**&36\\\hline \end{array}$$ Corresponding to each there exist only one way in bucket $4$. So probability is $1/36\approx2.77\%$