Distinguishable balls in distinguishable boxes?

Question

Suppose I have $n$ distinguishable balls and $N$ distinguishable boxes. A particular configuration of this 'system' is such that there are $k$ particles in a box, b, where $1\lt b \lt N$ (i.e. the boxes are numbered). The ordering of balls in a particular box does not matter. The number of ways of realising a particular configuration is:

$$n! \prod_{k=1}^{N}\frac{1}{k!}$$

I'm struggling to show that the above is true. My current thoughts (though they are wrong) are:

ways of producing particular configuration =
(ways of choosing $k$ balls from $n$ balls) x (ways of choosing 1 box from $N$ boxes) x
(ways of choosing $n-k$ balls from $n$ balls) x (ways of choosing $N-1$ boxes from $N$ boxes) =
$$nC_k \times NC_1 \times nC_{n-k} \times NC_{N-1} $$

Would anyone be willing to help me figure this out?

I was asked: The statement is not clear to me. Isn't your description of a valid configuration equivalent of saying : "put n balls in N boxes such that (at least) one box has exactly k balls" ? - Yes, this is what I mean.

Answer 1

I am going to assume that there are $n_k$ balls in box $k$ for each $k$ in $\{1,2,\ldots,N\}$. So $\displaystyle n=\sum_{k=1}^N n_k$.

So you can choose $n_1$ balls to put in box $1$ in $\displaystyle { n\, \choose n_1}=\dfrac{n!}{n_1!(n-n_1)!}$ ways. Once you have done that, you can choose $n_2$ of the remaining balls to put in box $2$ in $\displaystyle { n-n_1 \choose n_2}=\dfrac{(n-n_1)!}{n_2!(n-n_1-n_2)!}$ ways. And so on.

That makes the total number of ways of getting the $(n_1,n_2,\ldots,n_N)$ distribution:

$$\displaystyle \dfrac{n!}{n_1!{(n-n_1)!}} \times \dfrac{(n-n_1)!}{n_2!(n-n_1-n_2)!} \times \cdots \times \dfrac{(n-n_1-\cdots- n_{N-1})!}{n_N!(n-n_1-\cdots- n_{N-1}-n_N)!}$$ which allows you to cancel most of the numerator and almost half the denominator to give $\displaystyle \dfrac{n!}{n_1!\, n_2!\,\cdots \,n_N! \,0!} = n! \prod_{k=1}^{N} \dfrac{1}{n_k!} $ as I think you intended. This is called the multinomial coefficient.

Answer 2

I know that the answer for this question when n = 2 and N = 3 is 12. Here is how. Suppose we have three bins B1, B2 and B3 and two balls b1 and b2.

The first 4 assignments correspond to the scenario when the bin B1 is empty, and the two balls are distributed in the bins B2 and B3. This can be done on 4 different ways: (i) b1 in B2 and b2 in B3, (ii) b2 in B2 and b1 in B3, (iii) b1 and b2 in B2 and B3 is empty and (iv) b1 and b2 in B3 and B2 is empty. Similarly 4 other assignments will be possible with the bin B2 being empty and 4 more assignments when B3 is empty. As such the total number of ways of distributing 2 balls in 3 bins will be 12.

This example can be used to verify any answer (the function of n and N) if it's correct.

I am looking for this function. If anyone knows this function, please post it on this forum.