Probability of throwing balls into bins

[benchbreaker]

Hi, i have a couple of problems that I am not sure about (i get the wrong answer for particular cases because the probability add up to more than 1)

say you have 50 balls and 20 bins, you throw all 50 balls into the bins, with equal probability of a ball landing in each bin

1. what is the probability that at least one of the bins has more than 5 balls?

2. what's the probability at least 3 bins are empty?

are there any general formulas for b balls, n bins, more than x balls in at least one bin and at least y bins empty?

P.S this is the same problem as rolling a 20 sided dice 50 times i think, might help

 

[SW VandeCarr]

Hi, i have a couple of problems that I am not sure about (i get the wrong answer for particular cases because the probability add up to more than 1)

say you have 50 balls and 20 bins, you throw all 50 balls into the bins, with equal probability of a ball landing in each bin

1. what is the probability that at least one of the bins has more than 5 balls?

2. what's the probability at least 3 bins are empty?

are there any general formulas for b balls, n bins, more than x balls in at least one bin and at least y bins empty?

P.S this is the same problem as rolling a 20 sided dice 50 times i think, might help

There may be a direct combinatorial solution for this problem, and I'll wait for someone else to post one. So far, no one has. I'm going to suggest an easier way based on normal theory. While you said that each bin has an equal probability of catching a ball, the distribution of the individual bin totals over time is expected to be normal with repeated experiments. The expectation for each bin is 2.5. Viewing this as a goodness of fit type problem, the variance for each bin corresponds to twice the degrees of freedom of n-1=19 or 38.. The square root of this is the standard deviation estimate which is 6.16. (5-2.5)/6.16= 0.406 is the Z score estimate. Look up the probability that corresponds to this for the normal distribution. For 0 balls in a bin this value will be the same. (It just works out this way from your numbers). For three such bins, multiply the probabilities.

If I'm wrong, someone will tell me although I don't think I'm way off. You would expect the probability of at least one departure of a given magnitude from the group mean will increase with increasing df.

 

[chiro]

There may be a direct combinatorial solution for this problem, and I'll wait for someone else to post one. So far, no one has. I'm going to suggest an easier way based on normal theory. While you said that each bin has an equal probability of catching a ball, the distribution of the individual bin totals over time is expected to be normal with repeated experiments. The expectation for each bin is 2.5. Viewing this as a goodness of fit type problem, the variance for each bin corresponds to twice the degrees of freedom of n-1=19 or 38.. The square root of this is the standard deviation estimate which is 6.16. (5-2.5)/6.16= 0.406 is the Z score estimate. Look up the probability that corresponds to this for the normal distribution. For 0 balls in a bin this value will be the same. (It just works out this way from your numbers). For three such bins, multiply the probabilities.

If I'm wrong, someone will tell me although I don't think I'm way off. You would expect the probability of at least one departure of a given magnitude from the group mean will increase with increasing df.

Great idea! I was thinking along the lines of combinatorial probability representations as well, but if the OP can accept some form of error, this is a great method.

 

[DrBloke]

I believe solving this problem is what you do to derive the Maxwell-Boltzman distribution of energies in molecules at equilibrium, although in that case you have a very large number of bins (molecules) and balls (energy). That might be a good starting point for researching for a combinatorial solution. I would look myself, but I've been enjoying trying to derive the answer to your problem myself in my free time over the last few weeks and I don't want to see the answer yet. I wouldn't wait for me though. My maths isn't that great and it's going to take me another few weeks at least. But I may get back in touch when I get a solution to see how you did it in the end.

I don't think it's the same as the 20 sided dice problem because in that case each roll is an independent event, whereas with the bins, if you have 5 balls in 10 separate bins then the probability of finding 5 balls in any of the rest is affected.

Sorry, this probably doesn't help you. It's more just a show of moral support.

 

[SW VandeCarr]

I believe solving this problem is what you do to derive the Maxwell-Boltzman distribution of energies in molecules at equilibrium, although in that case you have a very large number of bins (molecules) and balls (energy).

Thanks chiro and DrBloke. In this case we know the equilibrium condition. That is, the long term average of repeated experiments is a uniform distribution of 2.5 balls per bin (or in this case, exactly 10 bins with 3 balls and 10 bins with 2 balls). We can get the denominator of any probability we might want to consider: C(50,20) but the numerator is a problem when you ask for the specifics that the OP did. I agree this is not a 20 sided die problem where we could use the binomial theorem, at least as far as I can see.

Because I was in applied math, my preference was always the simplest solution that provided the required level of both precision and accuracy. I would really like to compare my estimate to a computationally exact solution, just as was done with another thread on this board re Easter egg probabilities.

BTW: C(50,20)=47,129,212,243,960 (from an online calculator).

 

[DrBloke]

SW VandeCarr: I like your way of doing this but am having some problems understanding it fully. You seem to suggest a normal distribution around a peak 2.5. I have a problem with this because if you imagine a 3 ball deviation from the mean then you get a problem. Of course it is possible to have 5 or 6 balls in a bin but it is not possible to have less than 0 balls in a bin. I suspect the distribution is not normal but a lopsided normal distribution, like the Maxwell-Boltzmann distribution. It goes down to zero on one side but could go as high as 50 (the total number of balls) on the other, since there is a small probability that random throwing could lead to all the balls going in one bin.

With regard to a combinatorial method, I agree the numerator is the bigger problem, but I don't think the denominator is as simple as you imply. C(50, 20) implies order doesn't matter, but the problem is the bins are not indistinguishable. 50 balls in bin 1 and none in the others is a different arrangement to 50 balls in bin 2 and none in the others. If you consider the simple case of distributing at random 3 ball in 3 bins then you find there are 10 ways to do this but C(3,3) = 1. I am close to coming up with a correct form of the denominator, but I warn it's not nice. I think the number will be bigger than the C(50,20) value you quote.

 

[SW VandeCarr]

SW VandeCarr: I like your way of doing this but am having some problems understanding it fully. You seem to suggest a normal distribution around a peak 2.5. I have a problem with this because if you imagine a 3 ball deviation from the mean then you get a problem. Of course it is possible to have 5 or 6 balls in a bin but it is not possible to have less than 0 balls in a bin. I suspect the distribution is not normal but a lopsided normal distribution, like the Maxwell-Boltzmann distribution. It goes down to zero on one side but could go as high as 50 (the total number of balls) on the other, since there is a small probability that random throwing could lead to all the balls going in one bin.

I agree. However, the probability distribution does not go to zero with zero balls. It is non-zero. In fact it is the same as the probability as 5 balls given the expectation of 2.5. This expectation for each bin is guaranteed from the specification of the problem: 20 bins; 50 balls randomly scattered with each bin having an equal probability. So the distribution in each bin over many trials would be "symmetric" but "cut off" on the left side. This cut off at zero is often seen with the Poisson distribution which is a variant of the normal but it is not symmetric. I considered the Poisson distribution for the individual bins but we need to consider the degrees of freedom in the calculation, motivating the chi square distribution which is the distribution of the squared deviations from the mean of the normal distribution of n observations, each observation being one degree of freedom with k=df=n-1.

I dohn't think the denominator is as simple as you imply. C(50, 20) implies order doesn't matter, but the problem is the bins are not indistinguishable. 50 balls in bin 1 and none in the others is a different arrangement to 50 balls in bin 2 and none in the others. If you consider the simple case of distributing at random 3 ball in 3 bins then you find there are 10 ways to do this but C(3,3) = 1. I am close to coming up with a correct form of the denominator, but I warn it's not nice. I think the number will be bigger than the C(50,20) value you quote.

The question is how many ways are there to choose subsets of size 20 from a set of of size 50 without regard to order since that's not part of the OPs question. So any random arrangement of 20 numbers from zero to 50 that total 50 would qualify as a choice. The number of bins and the total number of balls is fixed. So if we get 50 balls in (any) one bin, all the other bins must be empty.

EDIT: I think I found a partial answer. The number of ways n things can go into k bins is (n+k+1)!/k!(n-1)!.

 

[DrBloke]

I just wrote a long reply which I lost (that's what comes with being a noob). I have a similar answer to you but slightly different:
C((n+k-1),(k-1))

which is (n+k-1)!/(k-1)!(n-2)!

This gives 10 for putting 3 balls into 3 cups which is what I mentioned above. Here are the 10 ways:

300
210
201
120
102
111
030
003
021
012

I hold that order is important in calculating the size of the sample space.

Your formula gives 420 for 3 balls in 3 cups, which is wrong, but I suspect you have just made an arithmetic error somewhere in deriving your formula

For 50 balls in 20 cups there are a massive 4.6e16 ways

 

[DrBloke]

It's interesting to note that for 1 bin there is only one way. All the balls go in the one bin. For two cups there are k+1 ways (n=number of balls, k = number of cups) taking 7 balls for some examples:

70
61
51
41
31
21
11

n+1 ways

for 3 cups it is the sum of the natural numbers from 1 to n+1, or the triangular numbers from 1 to n

for 4 cups it is the sum of the tetrahedral numbers

these correspond to columns 1, 2, 3 etc of Pascal's triangle.

 

[DrBloke]

I am part of the way to calculating the numerator but unfortunately here in the uk it's time for bed.

 

[SW VandeCarr]

I just wrote a long reply which I lost (that's what comes with being a noob). I have a similar answer to you but slightly different:
C((n+k-1),(k-1))

which is (n+k-1)!/(k-1)!(n-2)!

For 50 balls in 20 cups there are a massive 4.6e16 ways

Yes. I made a transcription error. My source was: (n+k-1)!/k!(n-1)! but yours is probably more accurate, especially for small numbers.
Yes, you can lose your post here in PF. Best to save parts of it and add it to it.

I am part of the way to calculating the numerator but unfortunately here in the uk it's time for bed.

Good luck. I haven't found anything. The numerator will be nearly as large as the denominator because the probabilities are large. My estimate for 5 or more balls in at least one bin for 19df is P=0.34. Regarding your log value, that's not to base e is it? That's only about 40,876,108. I'm thinking it's E representing base 10.

 

[SW VandeCarr]

To the extent skewness exists in the estimate, this can be adjusted by using the Poisson $$\lambda$$ for the right variance under a non central chi square distribution. The new mean is $$k+\lambda$$ and the variance is $$2(k+2\lambda)$$. $$\lambda = 2.5$$ so the new right variance is 48 and the right sd estimate is 6.92. So for the right, the new estimate of Z is (5-2.5)/6.93=0.3608. For the left side, no adjustment is made since I'm not calculating the full non central PDF and integrating. (If anyone wants to do it, let me know what you get please). The new right sided probability estimate for at least 5 balls in at least one bin is 0.36, up from 0.34. The left sided estimate for 0 balls stays the same as far as I'm concerned: $$(0.3424)^3= 0.04$$ for at least three empty bins.

 

[DrBloke]

Ok. I think I've got this. For n balls distributed randomly in N bins, the probability of picking a bin at random and finding x balls in it is:

C(n-x+N-2, N-2)/C(n+N-1, N-1)

which is the same as

(n-x+N-2)!(N-1)!n!/[(N-2)!(n-x)!(n+N-1)!]

for 50 balls distributed randomly between 20 bins the probability of finding 5 balls in a bin chosen at random is approximately 0.056. Though I realize that isn't quite the question. But I think my formulae will help.

yes SW VandeCarr I was using e to represent base 10. It's the computer programmer in me and I haven't figured out how to do fancy formulae on this editor yet.

The next step is to use some fancy approximation of large factorials (such as the Stirling approximation). This would enable plotting a distribution function, which I'm willing to bet looks like the Maxwell Boltzmann distribution, because it is the M-B distribution I believe.

 

[bpet]

Hi, i have a couple of problems that I am not sure about (i get the wrong answer for particular cases because the probability add up to more than 1)

say you have 50 balls and 20 bins, you throw all 50 balls into the bins, with equal probability of a ball landing in each bin

1. what is the probability that at least one of the bins has more than 5 balls?

2. what's the probability at least 3 bins are empty?

are there any general formulas for b balls, n bins, more than x balls in at least one bin and at least y bins empty?

P.S this is the same problem as rolling a 20 sided dice 50 times i think, might help

Both could be solved by Markov methods. To solve the second which is easier, let state k be the number of empty bins starting with k=m and adding one ball at a time k reduces by one with a probability k/m. The transition matrix is bidiagonal so the nth power has an explicit solution. For the first question, maybe there's a simpler way but I'd let each state be the vector (k_0,...,k_m) where k_j is the number of bins containing j balls. The number of states is the number of positive solutions to sum(j.k_j)<=n and this number could be further reduced using sum(j.k_j)=i where i is the number of balls thrown so far.

 

[SW VandeCarr]

for 50 balls distributed randomly between 20 bins the probability of finding 5 balls in a bin chosen at random is approximately 0.056. Though I realize that isn't quite the question. But I think my formulae will help.

next step is to use some fancy approximation of large factorials (such as the Stirling approximation). This would enable plotting a distribution function, which I'm willing to bet looks like the Maxwell Boltzmann distribution, because it is the M-B distribution I believe.

That might be correct for exactly five balls for a simple Poisson experiment (1 df) For at least 5 balls with $$\lambda=2.5$$, the probability is 0.1088. It is not the probability of finding 5 balls (exactly or at least) across twenty bins (19 df). Note also that the cumulative probability of at least 5 balls based on 20 independent Poisson experiments is much higher than my estimate of P=0.36. However, the chi square distribution is constrained by the sum of the observations of each degree of freedom.

The probability of exactly 5 with lambda=2.5 is 0.0668 (1df).

http://dostat.stat.sc.edu/prototype/calculators/index.php3?dist=Poisson

However this problem is for n-1=19 df. That greatly increases the probability that at least one bin will have at at least five balls.

EDIT: The MB distribution is a chi (not chi squared) distribution of a single parameter a which is a vector in 3 dimensions with 3 df.

 

[SW VandeCarr]

Both could be solved by Markov methods. To solve the second which is easier, let state k be the number of empty bins starting with k=m and adding one ball at a time k reduces by one with a probability k/m. The transition matrix is bidiagonal so the nth power has an explicit solution. For the first question, maybe there's a simpler way but I'd let each state be the vector (k_0,...,k_m) where k_j is the number of bins containing j balls. The number of states is the number of positive solutions to sum(j.k_j)<=n and this number could be further reduced using sum(j.k_j)=i where i is the number of balls thrown so far.

Thanks bpet. This might be a basis for a simulation. Any chance you could do it?

 

[SW VandeCarr]

To correct an error in my post #15, the df for a single value x(i), is zero. So my Poisson result for at least 5 given lambda=2.5 has a df of zero since there is no comparison value. In this case, it is a calculated value rather than an observed value. A df of 1 is n-1 implying 2 data values. This is important because the chi square is not defined for n-1 when n=1 since it is the distribution of the squared deviation from the expected value for n-1 degrees of freedom. This also true for my reference to the probability of exactly 5 balls later in the post. The df should be zero. We could say, in this situation, we observe 5 balls (x(i)) and we ask what the probability of 5 balls is given a prior expectation of 2.5. However, a simple Poisson estimate assumes the observation is independent and not part of the data from which the expectation is estimated.

I also erred when I said the chi square is constrained by the sum of the values represented by the degrees of freedom. It is constrained by the sum of the observations.

 

[bpet]

Both could be solved by Markov methods. To solve the second which is easier, let state k be the number of empty bins starting with k=m and adding one ball at a time k reduces by one with a probability k/m. The transition matrix is bidiagonal so the nth power has an explicit solution. For the first question, maybe there's a simpler way but I'd let each state be the vector (k_0,...,k_m) where k_j is the number of bins containing j balls. The number of states is the number of positive solutions to sum(j.k_j)<=n and this number could be further reduced using sum(j.k_j)=i where i is the number of balls thrown so far.

Further to this, it seems there are 204226 solutions to sum(j.k_j)=50, of which 181274 satisfy sum(k_j)<=20. So it would be feasible to work out the probability of each combination occurring with, say, an nx51 array where element (i,j) is the number of bins with (j-1) balls for the ith combination.

 

[SW VandeCarr]

I used a calculation from the uniform distribution for n=20 where the variance is given as:

$$((b-a+1)^2-1)/12$$. Numbering the bins 1-20 we get $$(400-1)/12 = 33.25$$

The square root is 5.766 so (5-2.5)/5.766 =0.4336 = Z. This Z value corresponds to P=0.3323 which compares to the value P=0.3424 for the original estimate from the chi square distribution unadjusted for skewness.

This seems to validate the chi square approach which I think is the more accurate estimate in this case. In any case, I'm fairly sure these estimates are reasonable. I'll leave any further effort for an exact value to bpet or anyone else to who wants to try. However, if any such value deviates very much from the values I've been getting by estimation, I won't believe it.

 

[awkward]

I haven't come up with an analytic solution, but I can offer approximate values based on Monte Carlo simulation.

I simulated throwing 50 balls into 20 bins 1,000,000 times. (I used Python, if anyone cares.) At least one bin contained more than 5 balls in 587,742 trials, and at least 3 bins were empty in 175,644 trials.

Using a standard method for computing confidence intervals on binomial proportions, 95% confidence intervals are 0.5868 to 0.5887 and 0.1756 to 0.1764 respectively.

[Edit] That second confidence interval should be 0.1749 to 0.1764. [/edit]

 

[SW VandeCarr]

I haven't come up with an analytic solution, but I can offer approximate values based on Monte Carlo simulation.

I simulated throwing 50 balls into 20 bins 1,000,000 times. (I used Python, if anyone cares.) At least one bin contained more than 5 balls in 587,742 trials, and at least 3 bins were empty in 175,644 trials.

Using a standard method for computing confidence intervals on binomial proportions, 95% confidence intervals are 0.5868 to 0.5887 and 0.1756 to 0.1764 respectively.

Like I said, I don't believe it. The cumulative probability of 20 independent trials, binomial or Poisson with mean 2.5, will give a higher probability than what I got, in fact I think higher than what you got. In this case, the probabilities are not independent. Any combination of balls in the bins must total N=50. The distribution across bins, over repeated trials, is assumed to be uniform with a tendency toward normal distributions in the individual bins (truncated on the left).

Why would the uniform and chi square distributions agree so well if they were not essentially correct? I showed all my work. If it's wrong, where is it wrong?

EDIT: As I think about this, what I've actually estimated is the probability of any random bin having 5 or more balls which is a different question then at least one bin with more than five balls. That would be a higher probability, so I yield to the power of numerical solutions. Also your simulation nicely took care of the skewness issue on the left. This is a bit difficult to deal with analytically.

 

[awkward]

Here is a simple approximation to the first question, the probability that at least one bin will have more than 5 balls.

Let's say the number of balls in bin i is $$X_i$$ for i = 1,2, ..., 20. The distribution of $$(X_1, X_2, \dots, X_{20})$$ is Multinomial, so the marginal distribution of $$X_i$$ is Binomial(n=50, p=1/20) for any i. So the probability that bin i has 5 or fewer balls is about 0.9622. The$$X_i$$'s are not independent, but let's pretend they are. After all, there are 20 bins, so we don't expect one bin's contents to have a major effect on the others. Pretending independence,

$$P(\text{at least one bin has more than 5 balls}) = 1 - P(\text{all bins have 5 balls or less}) = 1 - P(X_i \le 5)^{20} \approx 0.54$$

This isn't too far from the 0.58 value I obtained by simulation.

 

[SW VandeCarr]

The$$X_i$$'s are not independent, but let's pretend they are. After all, there are 20 bins, so we don't expect one bin's contents to have a major effect on the others. Pretending independence,

$$P(\text{at least one bin has more than 5 balls}) = 1 - P(\text{all bins have 5 balls or less}) = 1 - P(X_i \le 5)^{20} \approx 0.54$$

This isn't too far from the 0.58 value I obtained by simulation.

Yup! It's fairly straightforward if you assume (or pretend) independence. I just rejected that approach from the start because it isn't. This led me to the chi square goodness of fit approach (and to answering a different question). I think that if there were 100 bins, I would have considered it.

EDIT: I must admit that I don't know exactly what my result means if anything. The variances from the chi square and the uniform distributions closely agree which I would expect. I must be applying these parameters wrongly. Thanks for giving us the right answers awkward. If anyone can explain why using normal theory did not work, I'd appreciate it.

 

[SW VandeCarr]

I did an online calculation for the Poisson probability of at most five balls for lambda=2.5 and got a result closer than you did to your simulation result:

P(at most 5 balls)=0.9580; This result to the 20th power=0.4239. P(more than 5 balls)= 1-0.4239=0.5761

I wondering if statistical independence matters in problems like this. You could consider this a calculation based on long term averages of repeated experiments such that every bin is reduced to uniformity. I'm not concerned about larger numbers of bins, but can this be applied to smaller numbers of bins, say 5 or 10? It seems the same principle should hold.

However, its not clear to me that you can get the probability of three empty bins this way. It turns out that the probability of more than zero (0.9179 by the calculator) raised to the 20th power is 0.1821, but that's not what we're after. You can of course take the cube of the right side solution which gets you close to the left side solution:(P(0.588)^3= 0.203).

 

[awkward]

I continued to think about the problem and was able to find analytical (combinatorical) solutions to both parts. The results are consistent with the simulation results posted earlier.

For the probability that at least one bin has more than 5 balls, consider the complementary problem that all bins have less than or equal to 5 balls. An exponential generating function for n balls in 20 bins is

$$f(x) = \left( \sum_{i=0}^5 \frac{1}{i!} \left( \frac{x}{20} \right) ^i \right) ^{20}$$

The probability that all bins will have less than or equal to 5 balls after tossing n balls into the bins is the coefficient of x^n / n! when f is expanded. I used a computer algebra program to expand f and found that the coefficient of x^50 / 50! is 0.412758, approximately. The probability that at least one bin has more than 5 balls is 1 - 0.412758 = 0.587242.

For the probability that at least 3 bins are empty, we could use the generating function approach again, but instead I found a formula in "An Introduction to Probability Theory and Its Applications", Volume I, 2nd edition, by Feller, section IV.2. In Feller's notation, r = the number of balls, n = the number of cells, and $$p_m(r,n)$$ is the probability that exactly m cells are empty. The formula is

$$p_m(r,n) = \binom{n}{m} \sum_{\nu=0}^{n-m} (-1)^{\nu} \binom{n-m}{\nu} \left(1 - \frac{m+\nu}{n} \right) ^r$$

Using this formula we find
$$p_0(50,20) \approx 0.16418$$
$$p_1(50,20) \approx 0.35533$$
$$p_2(50,20) \approx 0.30456$$

The probability that at least 3 bins are empty is 1 minus the sum of the three preceding probabilities, about 0.17592.

For an easy approximation to this last problem, the probability that any given bin is empty is p = (19/20)^50. Two bin's being empty are not independent events, but it seems they are nearly so. If we make the false assumption that the bins are independent, the total number of empty cells has a Binomial distribution with n = 20 and p = (19/20)^50. If we compute the probability that the number of empty cells is at least 3 using this distribution we find the probability is 0.196, not too far from the exact result above.

 

[SW VandeCarr]

For the probability that at least 3 bins are empty, we could use the generating function approach again, but instead I found a formula in "An Introduction to Probability Theory and Its Applications", Volume I, 2nd edition, by Feller, section IV.2. In Feller's notation, r = the number of balls, n = the number of cells, and $$p_m(r,n)$$ is the probability that exactly m cells are empty. The formula is

$$p_m(r,n) = \binom{n}{m} \sum_{\nu=0}^{n-m} (-1)^{\nu} \binom{n-m}{\nu} \left(1 - \frac{m+\nu}{n} \right) ^r$$

Using this formula we find
$$p_0(50,20) \approx 0.16418$$
$$p_1(50,20) \approx 0.35533$$
$$p_2(50,20) \approx 0.30456$$

The probability that at least 3 bins are empty is 1 minus the sum of the three preceding probabilities, about 0.17592.

I'm assuming $$p_1$$ means the probability of exactly one zero. If so, the fact that $$p_1 = 0.355$$ is tantalizingly close to my initial result for both sides and has me wondering since 0 and 5 are equidistant from the mean of 2.5. This formula takes into consideration the degrees of freedom. However the distribution is truncated on the left so that probability would not include the tail of the full distribution on the left. Interesting.

 

[bpet]

...For the probability that at least one bin has more than 5 balls, consider the complementary problem that all bins have less than or equal to 5 balls. An exponential generating function for n balls in 20 bins is

$$f(x) = \left( \sum_{i=0}^5 \frac{1}{i!} \left( \frac{x}{20} \right) ^i \right) ^{20}$$

The probability that all bins will have less than or equal to 5 balls after tossing n balls into the bins is the coefficient of x^n / n! when f is expanded. I used a computer algebra program to expand f and found that the coefficient of x^50 / 50! is 0.412758, approximately. The probability that at least one bin has more than 5 balls is 1 - 0.412758 = 0.587242.

...

That's neat, could you explain how the generating function works?

 

[awkward]

That's neat, could you explain how the generating function works?

I'll try. An exponential generating function (EGF) maps a sequence to a function. If we have the sequence $$a_0, a_1, a_2, \dots$$, its EGF is, by definition,
$$\sum_{i=0}^{\infty} \frac{a_i}{i!}x^i$$

If we have 0 to 5 balls and 1 bin, in how many ways can we put n balls into the bin? Just 1 way, for n = 0, 1, 2, 3, 4, 5. This is the sequence (1, 1, 1, 1, 1, 1, 0, 0, 0, ...); its EGF is
$$\sum_{i=0}^5 \frac{1}{i!}x^i$$

Now suppose we have 2 bins and each can contain 0 to 5 balls. How many possibilities are there if there are n balls total? We consider the sequence in which the balls are tossed into the bins to be significant, not just the final totals in each bin. To get the EGF of the answer, we just multiply the EGFs of the possibilities for each of the two bins. I.e.,
$$\sum_{i=0}^5 \frac{1}{i!}x^i \cdot \sum_{j=0}^5 \frac{1}{j!}x^j = \left( \sum_{i=0}^5 \frac{1}{i!}x^i \right) ^2$$
This is almost magic, but it's because of a fundamental property of EGFs. If we have two EGFs,
$$\sum_{i=0}^{\infty} \frac{a_i}{i!}x^i$$ and $$\sum_{j=0}^{\infty} \frac{b_j}{i!}x^j$$
their product is the EGF
$$\sum_{n=0}^{\infty} \frac{c_n}{n!}x^n$$
where
$$c_n = \sum_r \binom{n}{r} a_r b_{n-r}$$
It may take a while for that to soak in.

Repeat this 20 times and we have that the EGF of the number of ways to toss 0 to 5 balls into each of 20 bins is
$$\left( \sum_{i=0}^5\frac{1}{i!}x^i \right)^{20}$$
Now the number of ways in which n balls can be tossed into 20 bins without any restriction on the number of balls per bin is $$20^n$$; so if we simply replace x with x/20 in the previous EGF, we get an EGF for the probability that there will be 5 or fewer balls in all the bins. The result is
$$\left( \sum_{i=0}^5\frac{1}{i!} \left( \frac{x}{20} \right) ^i \right)^{20}$$

 

[bpet]

I'll try. An exponential generating function (EGF) maps a sequence to a function. If we have the sequence $$a_0, a_1, a_2, \dots$$, its EGF is, by definition,
$$\sum_{i=0}^{\infty} \frac{a_i}{i!}x^i$$

If we have 0 to 5 balls and 1 bin, in how many ways can we put n balls into the bin? Just 1 way, for n = 0, 1, 2, 3, 4, 5. This is the sequence (1, 1, 1, 1, 1, 1, 0, 0, 0, ...); its EGF is
$$\sum_{i=0}^5 \frac{1}{i!}x^i$$

Now suppose we have 2 bins and each can contain 0 to 5 balls. How many possibilities are there if there are n balls total? We consider the sequence in which the balls are tossed into the bins to be significant, not just the final totals in each bin. To get the EGF of the answer, we just multiply the EGFs of the possibilities for each of the two bins. I.e.,
$$\sum_{i=0}^5 \frac{1}{i!}x^i \cdot \sum_{j=0}^5 \frac{1}{j!}x^j = \left( \sum_{i=0}^5 \frac{1}{i!}x^i \right) ^2$$
This is almost magic, but it's because of a fundamental property of EGFs. If we have two EGFs,
$$\sum_{i=0}^{\infty} \frac{a_i}{i!}x^i$$ and $$\sum_{j=0}^{\infty} \frac{b_j}{i!}x^j$$
their product is the EGF
$$\sum_{n=0}^{\infty} \frac{c_n}{n!}x^n$$
where
$$c_n = \sum_r \binom{n}{r} a_r b_{n-r}$$
It may take a while for that to soak in.

Repeat this 20 times and we have that the EGF of the number of ways to toss 0 to 5 balls into each of 20 bins is
$$\left( \sum_{i=0}^5\frac{1}{i!}x^i \right)^{20}$$
Now the number of ways in which n balls can be tossed into 20 bins without any restriction on the number of balls per bin is $$20^n$$; so if we simply replace x with x/20 in the previous EGF, we get an EGF for the probability that there will be 5 or fewer balls in all the bins. The result is
$$\left( \sum_{i=0}^5\frac{1}{i!} \left( \frac{x}{20} \right) ^i \right)^{20}$$

Nice - it takes a bit of thought but I see how it works now!