Math Q&A Part 2

Hoempa

Math Team
Apr 2010
2,780
361
My reasoning is as follows, found by a hint by you, Pero, as I was on a different track. Find the probability that all have at most 2 balls in them.

The amount of ways to assign 20 balls to 14 urns where each ball has at most 5 balls is the coefficient of x^20 in (1 + x + x^2 + x^3 + x^4 + x^5)^14, i.e.
310829610.

The amount of ways to assign 20 balls to 14 urns where each ball has at most 2 balls is the coefficient of x^20 in (1 + x + x^2)^14, i.e.
93093.

So the total probability is \(\displaystyle \frac{310829610-93093}{310829610} \approx 0.9997\)
 
Jun 2013
1,315
116
London, England
I knew there was something not quite right. Correction:

I'll label the urns and the balls. So, the total number of possibilities is \(\displaystyle 14^{20}\)

Let N(x, y, z) be the number of possibilities where there are x urns with no balls, y urns with 1 ball and z urns with 2 balls.

N(x, y, z) is the product of the number of patterns of this type and the number of possibilities for a specific pattern.

\(\displaystyle N(4, 0, 10) = \binom{14}{4} \frac{20!}{2^{10}} \)

\(\displaystyle N(3, 2, 9) = \binom{14}{3} \binom{11}{2} \frac{20!}{2^9}\)

\(\displaystyle N(2, 4, 8 ) = \binom{14}{2} \binom{12}{4} \frac{20!}{2^8}\)

\(\displaystyle N(1, 6, 7) = 14 \binom{13}{6} \frac{20!}{2^7}\)

\(\displaystyle N(0, 8, 6) = \binom{14}{8} \frac{20!}{2^6}\)

Let N be the sum of the above.

So, if p is the probability that there are at most two balls in any urn:

\(\displaystyle p = \frac{N}{14^{20}}\)

I get that p = 1.31% (approx).
 
Last edited:
Dec 2013
1,117
41
The total number of possibilities is not 14^20 because you did not assume that one of the 14 urns could contain 5 so it will be then excluded.
In fact the problem is similar to a deck of 70 cards where each number from 1 to 14 has 5copies. You pick randomly 20 cards from 70 so C(70,20) is the total number of possibilities.
 
Jun 2013
1,315
116
London, England
My reasoning is as follows, found by a hint by you, Pero, as I was on a different track. Find the probability that all have at most 2 balls in them.

The amount of ways to assign 20 balls to 14 urns where each ball has at most 5 balls is the coefficient of x^20 in (1 + x + x^2 + x^3 + x^4 + x^5)^14, i.e.
310829610.

The amount of ways to assign 20 balls to 14 urns where each ball has at most 2 balls is the coefficient of x^20 in (1 + x + x^2)^14, i.e.
93093.

So the total probability is \(\displaystyle \frac{310829610-93093}{310829610} \approx 0.9997\)
This looks good, but I'm wondering about this constraint of 5 balls. It seems to me that it doesn't affect the result (see earlier post), because if you get to 5 balls you already have 3. And, perhaps, all these combinations are no longer equally likely.

If you removed this constraint and took the coefficient of \(\displaystyle x^{20}\) in

\(\displaystyle (1 + x + x^2 ... x^{14})^{14}\)

Would you get the same answer as me? 98.69%

PS I think it all makes sense now.

The problem Hoempa solved assumed that if you try to put a 6th ball in an urn, then the game is over. Whereas, the problem I solved assumed that you choose a different urn for that ball (essentially excluding an urn when it's full).

In the second case, the 5-ball rule makes no difference.
 
Last edited:
Jun 2013
1,315
116
London, England
The total number of possibilities is not 14^20 because you did not assume that one of the 14 urns could contain 5 so it will be then excluded.
In fact the problem is similar to a deck of 70 cards where each number from 1 to 14 has 5copies. You pick randomly 20 cards from 70 so C(70,20) is the total number of possibilities.
I labelled the balls, which is why there are 14^20 possibilities.

The 5-ball rule makes no difference to this particular problem.
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
The 5-ball rule makes no difference to this particular problem.
I agree. You get exactly the same results for 2, 3, and 4 under either version. The only difference is that the "max 5" version discards information that the other retains.
 

Hoempa

Math Team
Apr 2010
2,780
361
I think the constraint at most 5 does affect the result. Now, we can't do 6,6,8,0,...,0, which is an extra option.

The coefficient of x^20 in (1 + x + x^2 + ... + x^14)^14 is 573046488, so without the constraint I get (573046488-93093)/573046488 ~= 0.99983754.

The problem I solve is as if you'd roll 14 dice, each having faces 0 through 5 for the total amount of possibilities, and see how many rolls give 20. Same for dice with faces 0 through 2. This way, 5,5,4,4,2,0,0,0,0,0,0,0,0,0 is different from 5,5,4,4,0,0,0,0,0,0,0,0,0,2 as desired.

Mobels post makes me doubt about my solution though. We could say for at most two that we have 2 cards of each such that the probability is ((C(70, 20) - C(28, 20)) / C(70, 20) ~= 0.9999999999808
 

Hoempa

Math Team
Apr 2010
2,780
361
The difference between my result and the result from Mobels idea comes form whether for example you count 4,4,4,4,4,0,0,0,0,0,0,0,0,0,0 as 1 possibilitie or as \(\displaystyle {20 \choose 4,4,4,4,4}\); the amount of ways to get that one.
 
Jun 2013
1,315
116
London, England
I tried it with smaller numbers: 5 balls, 3 urns, at most 2 balls in any urn.

Solution a:

Total possibilities: 3^5 = 243

Only pattern is (1, 2, 2). 3 cases of this pattern. 5!/4 = 30 possibilites in each case.

So, p (at most 2 in any urn) = 90/243 = 10/27

Solution b:

Coeff of x^5 in (1+x+x^2)^3 = 3

Coeff of x^5 in (1+x+...x^5)^3 = 21

So, p(at most 2 in any urn) = 1/7

So, as a tiebreaker, I did a probability tree ... and got 10/27.

I don't think I understand the polynomial solution well enough to see why it's wrong (if it is!).
 
Dec 2013
1,117
41
I tried it with smaller numbers: 5 balls, 3 urns, at most 2 balls in any urn.

Solution a:

Total possibilities: 3^5 = 243

Only pattern is (1, 2, 2). 3 cases of this pattern. 5!/4 = 30 possibilites in each case.

So, p (at most 2 in any urn) = 90/243 = 10/27

Solution b:

Coeff of x^5 in (1+x+x^2)^3 = 3

Coeff of x^5 in (1+x+...x^5)^3 = 21

So, p(at most 2 in any urn) = 1/7

So, as a tiebreaker, I did a probability tree ... and got 10/27.

I don't think I understand the polynomial solution well enough to see why it's wrong (if it is!).
Please can you list randomly 27 out of the 243 possibilities or even all the 243?
I`m asking you because I still do not understand your approach.

Thank you.
 
Similar Math Discussions Math Forum Date
General Math
General Math
General Math
General Math