Distinct Objects into Distinct Bins, each bin has a different number of objects

Question

I was curious about these types of distribution and combinatorics problems and going about solving them. Let's say there are 15 different fruits that are to be equally likely distributed among 6 distinct monkeys. What’s the probability that each of the 6 monkeys ends up with a different number of fruits? This would mean that each of the 6 monkeys gets 0, 1, 2, 3, 4, and 5 fruits in some order.

Answer 1

Because each monkey is equally likely to get each fruit, each way to distribute the fruits amongst the monkeys is equally likely, so we can find the probability of giving each monkey a different number of fruits by simply dividing the number of ways that we can give out the fruits such that each monkey has a different number by the total number of ways we can give out the fruits.

The total number of ways to give out the fruits is pretty clearly $6^{15},$ since each of the $15$ fruits has a choice of $6$ monkeys to go to. (we could show this as a one-to-one correspondence with $15$-digit numbers in base $6$ if you'd like)

Regarding the ways that we can give out fruits so that each monkey gets a different number, instead of thinking about handing the fruits out to the monkeys one at a time, let's say we instead arrange both the monkeys and the fruit in a line. Because we know what sizes the groups have to be, we can just consider giving each monkey in line a group of each size in order: the first monkey gets no fruit, then the second gets the first one, the third gets the next two, and so on. This gives us a distribution of fruit to monkeys for every pair of permutations of monkeys and fruits in our lines. Because there are $6$ unique monkeys and $15$ unique fruits, there are $6!\cdot 15!$ such pairs of orders.

But we're not quite done: consider what happens if we swap the second and third fruits in our line. The third monkey, who takes two fruits, will still get the same two fruits, so although the order of fruits has changed, the distribution of fruits to monkeys hasn't. This means that we're overcounting the number of distributions of fruits, but we can fix this if we look at all of these ways that we can change the order of fruits without changing the distribution.

The only action that changes either order without changing the distribution is by changing the orders of fruits within groups: if we move monkeys then each monkey we move gets a different number of fruits, and if we move fruits between groups then the monkeys which get those groups will get different fruits. So, by counting the number of ways we can reorganize the line while maintaining the groups, we can figure out the extent of the overcounting.

For a group of size $n,$ there are $n!$ ways to organize them, and because the set of possible orders of the line of fruits can be seen as a Cartesian product of the sets of the orders of the groups, to get the total number of reorganizations for the line while maintaining the groups we just take the product of these $n!$ terms. So for a set of groups of sizes $1,2,3,4$ and $5,$ this gives us that there are $(1!)(2!)(3!)(4!)(5!)$ ways to reorganize any line of fruits while maintaining the groups.

Because of this, each of our desired organizations of fruits will have exactly $(2!)(3!)(4!)(5!)$ pairs of lines which correspond to it out of the total $6! \cdot 15!,$ so the total number of ways to give out the fruits such that each monkey gets a different number is $\frac{6! \cdot 15!}{2! \cdot 3! \cdot 4! \cdot 5!}.$

Finally, this gives us a final probability of $$\frac{6! \cdot 15!}{2! \cdot 3! \cdot 4! \cdot 5! \cdot 6^{15}} \approx 0.058$$

which matches the result from the multinomial distribution when you account for the different ways we can order the monkeys, and matches some simple empirical trials.

---

I hope this helps! Sorry if it got a bit verbose, I thought that delving into some of the details might help build intuition for how certain things work - hard to tell sometimes exactly what should be taken for granted and what shouldn't.

Answer 2

Alternative approach:

Similar to Stephen Donovan's answer, I also favor expressing the probability combinatorically, as

$$\frac{N\text{(umerator)}}{D\text{(enominator)}}, \tag1 $$

where, for convenience, I set

$$D = 6^{(15)}.\tag2 $$

The computation for $D$ is explained by reasoning that each fruit has $6$ choices, as to which monkey it goes to. However, because this (convenient) computation for $D$ was used, the computation for $N$ must be done in a consistent manner. This means that the computation for $N$ must distinguish between (for example) a specific piece of fruit going to Monkey-1 and the same piece of fruit going to Monkey-2.

This computation of the numerator, $N$, is greatly simplified by realizing that the only acceptable distribution is for some groups of $5,4,3,2,1,0$ fruits, going to Monkey-1, Monkey-2, ..., Monkey-6, in some order.

So, my approach is as follows.

First, I will arbitrarily assume that Monkey-1, Monkey-2, ..., Monkey-6 get $5,4,3,2,1,0$ fruits, respectively. Then, I will adjust for the fact that (for example) any of the Monkeys could be receiving the $5$ fruits.

There are $~\displaystyle \binom{15}{5}~$ ways of selecting $5$ pieces of fruit to go to Monkey-1.

Once this is done, there will then be $~\displaystyle \binom{10}{4}~$ ways of selecting $4$ pieces of fruit to go to Monkey-2.

Once this is done, there will then be $~\displaystyle \binom{6}{3}~$ ways of selecting $3$ pieces of fruit to go to Monkey-3.

Once this is done, there will then be $~\displaystyle \binom{3}{2}~$ ways of selecting $2$ pieces of fruit to go to Monkey-4.

Once this is done, there will then be $~\displaystyle \binom{1}{1}~$ ways of selecting $1$ piece of fruit to go to Monkey-5.

Once this is done, there will then be $~\displaystyle \binom{0}{0}~$ ways of selecting $0$ pieces of fruit to go to Monkey-6.

Therefore, under the assumption that the groups of $5,4,3,2,1,0$ pieces of fruit go to Monkey-1, Monkey-2, ...,Monkey-6, respectively, the computation is

$$\binom{15}{5} \times \binom{10}{4} \times \binom{6}{3} \times $$

$$\binom{3}{2} \times \binom{1}{1} \times \binom{0}{0}$$

$$=~ \frac{(15)!}{(5!) \times (4!) \times (3!) \times (2!) \times (1!) \times (0!)}. \tag3 $$

The only adjustment needed to the computation in (3) above, to complete the computation of $N$ is to recognize that rather than having the groups of $5,4,3,2,1,0$ pieces of fruit, going specifically to Monkey-1, Monkey-2, ..., Monkey-6, you can have the monkeys permuted in $(6!)$ ways. Therefore, all that is necessary, to compute $N$ is to take the computation in (3) above, and multiply it by $(6!)$.

Therefore,

$$N = (6!) \times \frac{(15)!}{(5!) \times (4!) \times (3!) \times (2!) \times (1!) \times (0!)}. \tag4 $$

---

Final computation:

Putting (1), (2), and (4) together, you have that

$$\frac{N}{D}$$

$$= (6!) \times \frac{(15)!}{(5!) \times (4!) \times (3!) \times (2!) \times (1!) \times (0!)} \times \frac{1}{(6)^{15}}$$

$$= \frac{(6!) \times (15!)} {(5!) \times (4!) \times (3!) \times (2!) \times (1!) \times (0!) \times (6)^{(15)}}.$$

Answer 3

In order to solve your problem, you need to understand the way to compute the number of ways in which you can write the positive integer n as a sum of some ascending distinct positive integers, for example, you can write 5 in 3 different ways: 5, 1 + 4, and 2 + 3. Assume A[n][x] as the number of ways of writing positive integer n as a sum of ascending positive integers greater or equal to x. $$A[n][x] = A[n - x][x + 1] + A[n-(x + 1)][x + 2] + ... + A[0][n + 1]$$ This is the recurrence relation for computing A[n][x]. Base of the relation is A[0][y] = 1 for all ys. What we want is A[n][1]. You can accomplish this computation in $O(n^3)$ with Dynamic Programming. You can compute the Desired probability afterward.