0
$\begingroup$

I thought my problem was going to be a simple combination problem, but got stuck between two interpretations. Rephrased to balls and bins and smaller numbers. (Edit: Original problem below)

10 balls must be put into 3 bins. Bin #1 must have between 3 and 5 balls, Bin #2 between 0 and 5 balls, and Bin #3 between 2 and 5 balls. (All intervals inclusive). What is the most likely allocation?

Method 1: Enumerate all 12 combinations that the sum equals 10, and each bin has values within their respective ranges

Case Bin1 Bin2 Bin3
A    3    2    5
B    3    3    4
C    3    4    3
D    3    5    2
E    4    1    5
F    4    2    4
G    4    3    3
H    4    4    2
I    5    0    5
J    5    1    4
K    5    2    3
L    5    3    2

B, C, G all tie with 4,200 combinations (e.g. 10!/(3!3!4!)) Which is (3,3,4) balls (for B)

Method 2: We know each bin must have a minimum number of balls, those are deterministic. Allocate those first. The remaining 5 balls must be allocated such at most two are placed in Bin 1, at most 5 in Bin 2, and at most 3 in Bin 3.

Case Bin1 Bin2 Bin3
A    0    2    3
B    0    3    2
C    0    4    1
D    0    5    0
E    1    1    3
F    1    2    2
G    1    3    1
H    1    4    0
I    2    0    3
J    2    1    2
K    2    2    2
L    2    3    1

F,J,K all tie with 30 combinations (e.g. 5!/(1!2!2!)) Which, adding back the balls already placed, yield (4,2,4) (for F)

EDIT: (original problem) Saw these two paragraphs in a book and was trying to re-derive the formulas

Suppose $N$ balls are to be distributed among $n$ boxes in such a way that the $i$th box does not contain less than $Na_i$ balls and no more then $Nb_i$ balls ($0 \le a_i < b_i \le 1$), then the number of ways in which the $i$th box receives the $Np_i$ balls is given by

$$W = \frac{[N(b_1+\dots+b_n)]!}{[N(a_1+\dots+a_n)]! \prod_{i=1}^n (N p_i - N a_i)! (N b_i - N p_i)!}$$

[...]

We now consider directly in terms of balls in the $n$ boxes, rather than in terms of probabilities. Suppose we want that the number of balls in the $i$th box should be between $l_i$ and $m_i$, then the number of ways of getting $n_1, n_2, \dots, n_n$ balls in the $n$ boxes is

$$W = \frac{(m_1+\dots+m_n)!}{(l_1+\dots+l_n)! \prod_{i=1}^n (n_i-l_i)! (m_i-n_i)!}$$

$\endgroup$
  • $\begingroup$ As you say, the probabilities will depend on how you place balls in bins while meeting the constraints. Perhaps you should tell us the original problem with its actual method of distribution $\endgroup$ – Henry Mar 22 '16 at 15:30
  • $\begingroup$ Thanks. Edited it for clarity and added original problem. $\endgroup$ – sheppa28 Mar 22 '16 at 15:43
  • $\begingroup$ I don't understand the connection between the top part and the "original problem". There's no talk of likely allocations in the original problem, so the original problem doesn't seem to throw any light on what you mean by that -- or am I missing something? $\endgroup$ – joriki Mar 22 '16 at 16:32
  • $\begingroup$ In the book they were trying to find the allocation which maximized the multiplicity W. I might have misinterpreted it when rephrasing to most likely allocation. It is the multiplicity expression I am trying to re-derive. The simplified version came out by trying to run their answers on small numbers for understanding. $\endgroup$ – sheppa28 Mar 22 '16 at 16:39

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.