Exercise 3.5 from Jaynes' Probability Theory - induction?

Question

N balls are tossed into M urns; there are evidently $M^N$ ways this can be done. If we consider them all equally likely, what is the probability that each urn receives at least one ball?

I tried solving this by induction, or trial, and came to the following result: $$\frac{\binom{M}{N-M}}{M^N}$$ Is it correct? Is there any other way to find it?

---

Now that I've thought about the denominator for a while, it doesn't sound quite right. Conventioning right now that 'xyz...' means 'x balls in urn 1, y balls in urn 2, z balls in urn 3 and so on,' T(M, N) = number of possible distributions of N balls into M urns, F(M,N) = number of distributions of N balls into M urns with at least one ball per urn:

N balls into 1 urn: N (T(1, N) = 1 distribution, F(1,N≠0) = 1 distribution)

1 ball into 2 urns: 10 01 (T(2,1) = 2 distributions, F(2,1) = 0 distributions)

2 balls into 2 urns: 20 11 02 (T(2,2) = 3 distributions, F(2,2) = 1 distribution)

3 balls into 2 urns: 30 21 12 03 (T(2,3) = 4 distributions, F(2,3) = 2 distributions)

2 balls into 3 urns: 200 110 101 020 011 002 (T(3,2) = 6 distributions, F(3,2) = 0 distributions)

3 balls into 3 urns: 300 210 201 120 111 102 030 021 012 003 (T(3,3) = 10 distributions, F(3,3) = 1 distribution)

4 balls into 3 urns: 400 310 301 220 211 202 130 121 112 103 040 031 022 013 004 (T(3,4) = 15 distributions, F(3,4) = 3 distributions)

5 balls into 3 urns: 500 410 401 320 311 302 230 221 212 203 140 131 122 113 104 050 041 032 023 014 005 (T(3,5) = 21 distributions, F(3,5) = 6 distributions)

1 ball into 4 urns: 1000 0100 0010 0001 (T(4,1) = 4 distributions, F(4,1) = 0 distributions)

2 balls into 4 urns: 2000 1100 1010 1001 0200 0110 0101 0020 0011 0002 (T(4,2) = 10 distributions, F(4,2) = 0 distributions)

3 balls into 4 urns: 3000 2100 2010 2001 1200 1110 1101 1020 1011 1002 0300 0210 0201 0120 0111 0102 0030 0021 0012 0003 (T(4,3) = 20 distributions, F(4,3) = 0 distributions)

4 balls into 4 urns: 4000 3100 3010 3001 2200 2110 2101 2020 2011 2002 1300 1210 1201 1120 1111 1102 1030 1021 1012 1003 0400 0310 0301 0220 0211 0202 0130 0121 0112 0103 0040 0031 0022 0013 0004 (T(4,4) = 35 distributions, F(4,4) = 1 distribution)

5 balls into 4 urns: 5000 4100 4010 4001 3200 3110 3101 3020 3011 3002 2300 2210 2201 2120 2111 2102 2030 2021 2012 2003 1400 1310 1301 1220 1211 1202 1130 1121 1112 1103 1040 1031 1022 1013 1004 0500 0410 0401 0320 0311 0302 0230 0221 0212 0203 0140 0131 0122 0113 0104 0050 0041 0032 0023 0014 0005 (T(4,5) = 56 distributions, F(4,5) = 4 distributions)

From those numbers, it looks like $T(M,N) = \binom{N+M-1}{M-1}$ and $F(M,N) = \binom{N-1}{M-1}$. So that would make the probability of having at least one ball in each urn, throwing N balls into M urns, go as: $$p(M,N) = \frac{F(M,N)}{T(M,N)} = \frac{\binom{N-1}{M-1}}{\binom{N+M-1}{M-1}} = \frac{N!(N-1)!}{(N-M)!(N+M-1)!}$$

That doesn't look one bit like the stirling numbers, however, or like the answer you gave me... So, where did I go wrong in my steps?

---

Okay, I completely failed to consider this: he wants me to distinguish the ways that will lead to a certain final ball-urn state, not only the final states themselves, in which case I count 300 only once, but 210 counts 4 times and 111 counts 6 times. So much for my induction on the final sates...

So, using the Stirling numbers, that would make the final answer:

$$P(M,N) = \frac{\frac{1}{k!}∑_{j=0}^M(-1)^{M-j}\binom{M}{j}j^N}{M^N}$$

That being said, I wonder how I was expected to come to this conclusion, without previous knowledge of the Stirling numbers. Obviously I was supposed to reason them out, but I don't quite see how. Of course that is a fact about my ignorance and not about the problem itself. I shall work on it.

---

Further reading on the Stirling numbers of the second kind article on Wikipedia shows that these numbers are supposed to represent ways to put the balls into unlabelled urns, which would make the following two paths equivalent:

10 -> 20 -> 21

01 -> 02 -> 12

Which they clearly are not, in the problem, because otherwise there wouldn't be $M^N$ ways to fill the urns.

In that case, I will remain working on the problem, but what would such a solution look like?

---

Alright, so, following your lead, I got to:

$$p(M,N) = 1 - \frac{∑_{j=1}^{M-1}(-1)^{j+1}\binom{M}{j}(M-j)^N}{M^N}$$

And the results agree with induction. I wonder if there are any other possible ways to solve this?

Answer 1

The denominator you used is right, but the numerator is not. For the right thing, you should look at Stirling numbers of the second kind.

There is also a pleasant but not very useful Inclusion/Exclusion expression. Maybe that's what the exercise is looking for.

We find instead the number of ways that we can end up with at least one empty urn. The number of ways the $i$-th urn can be empty is the number of ways to distribute the balls among $M-1$ urns. By the reasoning you used, this is $(M-1)^N$.

Add up over all $i$. We get $$M(M-1)^N.\tag{$1$}$$

But Expression $(1)$ double counts the arrangements in which urns $i$ and $j$ are both empty. The number of ways urns $i$ and $j$ can be empty is $(M-2)^N$. Add up over all (unordered) pairs. We get $\binom{M}{2}(M-2)^N$.

This needs to be subtracted from $(1)$.

But we have subtracted too much, for we have doubly subtracted the patterns in which for example urns $i$, $j$, and $k$ are empty.

So we must add back $\binom{M}{3}(M-3)^N$.

Continue.