# Probability (n balls and n containers) **URL:** \ **Category:** Factual Questions\ **Created:** [August 11, 2004, 10:36pm UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443 "2004-08-11T22:36:09Z")\ **Posts on this page:** 20\ **Page:** 2
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 12, 2004, 5:26am UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/21 "2004-08-12T05:26:34Z")
> [@Cabbage](#): > > If the balls are indistinct and the containers are distinct, the number of ways to distribute n balls into n containers is C(2n-1,n). Let me know if you don’t see where that comes from. It’s not obvious to me–mind explaining? ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [August 12, 2004, 5:47am UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/22 "2004-08-12T05:47:32Z")
**ultrafilter** , to illustrate a specific example, let’s say I’m distributing 5 indistinct balls into 5 distinct containers. I can represent a particular distribution as the string bb|b||b|b The dividers ("|") represent the way the balls are partitioned into the containers. In other words, this string represents 2 balls in the first container, one in the second, none in the third, one in the fourth, and one ball in the fifth container. Another string (representing another distribution), could be bbbb||||b (Four balls in the first container, one ball in the fifth container, no other balls). Or bb||bb||b (Two balls in the first, two balls in the third, one ball in the fifth). Anyway, all of these strings have 5 "b"s (the five balls to be distributed) and 4 "|"s (to partition the string into the five containers). So I can describe any distribution by taking a “blank” string of 9 characters: * * * and choosing which 5 of those characters will be "b"s (or, equivalently, which 4 will be "|"s). So the number of ways to distribute 5 indistinct balls into 5 distinct containers is C(9,5). In general, the number of ways to distribute r indistinct objects into n distinct containers is C(n+r-1,r). ---
**Author:** ![CaptainMyrrh](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@CaptainMyrrh](https://boards.straightdope.com/u/CaptainMyrrh)\ **Post date:** [August 12, 2004, 6:05am UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/23 "2004-08-12T06:05:02Z")
I’ll give one last shot at trying to make my problem clear, and I apologize for the confusion (I think we have it already though). The problem came on the final in my probability class, and so I can’t be sure what exactly what was trying to be asked, but the way I had been working on it, and which I believe I was asking was: Balls indistinct, containers distinct, placement of the balls is random (Each ball is as likely to go into any container as any other) . I’m not exactly sure what you mean by uniform arrangement distributions, but I don’t think thats how I meant to ask it. If you could possibly rephrase that I could maybe clear it up. But, really just comes down to this. Probability of ball going into any one container is 1/n, which ball doesn’t matter, which container does. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [August 12, 2004, 6:33am UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/24 "2004-08-12T06:33:02Z")
> [@](#): > > I’m not exactly sure what you mean by uniform arrangement distributions, but I don’t think thats how I meant to ask it. If you could possibly rephrase that I could maybe clear it up. The distinction I was making there was the question over what was to be counted. For example, say there’s 2 indistinct balls and 2 distinct containers. We can count the ways they can be distributed. This is clearly 3–the arrangements (2,0), (1,1), and (0,2). When I spoke of “uniform arrangement distributions”, what I was trying to say was that we can speak of the probabilities in question by modeling it so that any arrangement is as likely as any other arrangement. In other words, each of the three arrangements has 1/3 chance occurring, and so the probability of exactly one being empty is 2/3. However, as **Josh\_dePlume** correctly pointed out, if the problem states that each ball has an equal chance of going into any particular container, then that changes things. For example (2 balls, 2 containers again), the probability that _both_ balls go in the first container is (1/2)\*(1/2) = 1/4. So the arrangements don’t have equal probabilities–(2,0) has 1/4 chance, (0,2) has 1/4 chance, but (1,1) has 1/2 chance. As I understand your question now, **Josh\_dePlume** ’s correction is the way to go. In fact, even though the balls are indistinct, I believe that the probabilities of the various arrangements will be such that we can do this problem the way the previous posters were calculating it (by assuming the balls are distinct). ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [August 12, 2004, 6:57am UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/25 "2004-08-12T06:57:52Z")
> [@CaptainMyrrh](#): > > There are n balls and n containers. If the balls are distributed at random (Prob. 1/n for each container), what is the probability that exactly one container remains empty? > > I just can’t seem to figure out an answer for this, and would surely love some help. Every path I’ve taken seems to be a dead end! > Any help would be much obliged. > > -Captain Myrrh I think everyone’s assuming that the balls are distinguishable. If not, then a given distribution looks like O|O|OOO|O|…||O|O|O|O| That is: an arrangement of n Os and n-1 |s (think of them as walls), with the Os and |s identical. There are (2n-1)!/n!(n-1)! such. To have exactly one empty is basically to pick one container to be empty and another to add the extra ball into. There are n choices for the first and n-1 for the second, for n(n-1) possibilities. Thus the probability is n!n(n-1)!(n-1)/(2n-1)! ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [August 12, 2004, 7:14am UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/26 "2004-08-12T07:14:58Z")
**Mathochist** , I believe you’re making the same mistake I made earlier. The distribution of the balls is uniformly random (each ball has a 1/n chance of going into a given container), however, the resulting arrangements of balls are not equally likely. For example, with two balls, two containers, there are only three arrangements: (2,0), (1,1), and (2,0). However, (1,1) is twice as likely to occur as either of the other two (1/2 versus 1/4). ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [August 12, 2004, 7:25am UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/27 "2004-08-12T07:25:06Z")
> [@Cabbage](#): > > **Mathochist** , I believe you’re making the same mistake I made earlier. The distribution of the balls is uniformly random (each ball has a 1/n chance of going into a given container), however, the resulting arrangements of balls are not equally likely. > > For example, with two balls, two containers, there are only three arrangements: (2,0), (1,1), and (2,0). However, (1,1) is twice as likely to occur as either of the other two (1/2 versus 1/4). Well, I see further down the thread where the OP’er _finally_ specified that the balls are not distinguishable, but that the jars are. i.e.: it’s not a mistake, but a valid choice given the OP. The biggest problem nonmathematicians have with mathematics is that they don’t know how to concisely and uniquely state a problem. ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [August 12, 2004, 7:27am UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/28 "2004-08-12T07:27:40Z")
> [@Mathochist](#): > > Well, I see further down the thread where the OP’er _finally_ specified that the balls are not distinguishable, but that the jars are. i.e.: it’s not a mistake, but a valid choice given the OP. > > The biggest problem nonmathematicians have with mathematics is that they don’t know how to concisely and uniquely state a problem. Incidentally, for an example of where the “containers” are distinct, the “balls” aren’t, and my reasoning still holds, consider n bosons occupying an n-degenerate set of states. 😃 ---
**Author:** ![BrotherCadfael](https://avatars.discourse-cdn.com/v4/letter/b/977dab/32.png) [@BrotherCadfael](https://boards.straightdope.com/u/BrotherCadfael)\ **Post date:** [August 12, 2004, 11:34am UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/29 "2004-08-12T11:34:33Z")
By the way, the cannonical term for the “containers” in this type of problem is “urns”. It has been observed that there are only three types of urns: Funeral urns, Grecian urns\*, and statistical urns. - Per Hermione Gingold ---
**Author:** ![Giles](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/giles/32/60_2.png) [@Giles](https://boards.straightdope.com/u/Giles)\ **Post date:** [August 12, 2004, 1:26pm UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/30 "2004-08-12T13:26:05Z")
I’m going to assume that the balls and urns are distinct. There are n^n ways of distrubuting the balls in the urns. If one urn is empty, then: (1) There are n ways of choosing that empty urn (2) There are n-1 ways of choosing the urn with 2 balls (3) There are n!/2 ways of arranging the balls in the urns with one ball each. Each of those is independent, and given those three conditions, the identity of the 2 balls in the urn with 2 balls is determined. So the chance that there there is just 1 empty urn is: ((n-1)_n!)/(2_(n^(n-1))) (I’ve cancelled out a common factor of n in that expression) Using Excel, I’ve calculated the value of that formula for n=2,3,…12: 2 0.5000000 3 0.6666667 4 0.5625000 5 0.3840000 6 0.2314815 7 0.1285179 8 0.0672913 9 0.0337196 10 0.0163296 11 0.0076948 12 0.0035457 ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [August 12, 2004, 3:18pm UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/31 "2004-08-12T15:18:36Z")
> [@BrotherCadfael](#): > > By the way, the cannonical term for the “containers” in this type of problem is “urns”. [nitpick] **Brother** , I’m shocked you don’t remember “canon” law (not “cannon”). What would the Pope say?[/nitpick] > [@](#): > > It has been observed that there are only three types of urns: Funeral urns, Grecian urns\*, and statistical urns. Which is the bad one, then? Obviously the good ones come in pairs, since “one good urn deserves another”. ---
**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\ **Post date:** [August 12, 2004, 5:24pm UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/32 "2004-08-12T17:24:58Z")
> [@Giles](#): > > So the chance that there there is just 1 empty urn is: > ((n-1)_n!)/(2_(n^(n-1))) > (I’ve cancelled out a common factor of n in that expression) ((n - 1) \* n!)/(2 \* n[sup]n-1[/sup]) = (n \* (n-1) \* n!)/( 2 \* n[sup]n[/sup]) = ((n \* (n-1))/(2 \* 1)) \* n! / n[sup]n[/sup] = [sub]n[/sub]C[sub]2[/sub] \* n! / n[sup]n[/sup] Which is what I posted oh, about 20 posts ago. ---
**Author:** ![CaptainMyrrh](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@CaptainMyrrh](https://boards.straightdope.com/u/CaptainMyrrh)\ **Post date:** [August 12, 2004, 6:25pm UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/33 "2004-08-12T18:25:17Z")
> [@Mathochist](#): > > The biggest problem nonmathematicians have with mathematics is that they don’t know how to concisely and uniquely state a problem. Apparently, its also a problem with mathematicians. The wording of my original quesiton was taken verbatim from the problem on my final, which was undoubtedly written by a mathematician. Where the problem became more unique and concise was when the non-mathematician clarified. ---
**Author:** ![b\_anthracis](https://avatars.discourse-cdn.com/v4/letter/b/7ea924/32.png) [@b\_anthracis](https://boards.straightdope.com/u/b_anthracis)\ **Post date:** [August 12, 2004, 7:46pm UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/34 "2004-08-12T19:46:47Z")
My sincerest apologies that the only link I could find to this particular piece of information generates an instant pop-up ad, but after fifteen years of non-use coupled with the realization that after I completed my multivariable calculus final exam I had lost the ability to perform SIMPLE functions (e.g., figuring out taxation levels as percentages at the gas pump), I feel obliged to toss a bit-o-levity in to the discussion: [Tom Lehrer’s “New Math”](http://www.sing365.com/music/lyric.nsf/SongUnid/EE27EF26A4F581BE48256A7D002575E1) Your friendly Anthrax-curative QC rep, b\_anthracis ---
**Author:** ![Josh\_dePlume](https://avatars.discourse-cdn.com/v4/letter/j/bbe5ce/32.png) [@Josh\_dePlume](https://boards.straightdope.com/u/Josh_dePlume)\ **Post date:** [August 12, 2004, 10:39pm UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/35 "2004-08-12T22:39:22Z")
> [@Mathochist](#): > > Well, I see further down the thread where the OP’er _finally_ specified that the balls are not distinguishable, but that the jars are. i.e.: it’s not a mistake, but a valid choice given the OP. I don’t see why it matters whether we say that the balls are distinguishable or not, so long as we say that their locations are independent (and if we don’t say that, we can get any aswer we like that’s between zero to one). If someone asked for the probability of two heads when two fair coins were flipped, it wouldn’t make sense to ask whether the coins were distinguishable. And I though balls were fermions. ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [August 13, 2004, 5:28pm UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/36 "2004-08-13T17:28:58Z")
> [@Josh\_dePlume](#): > > I don’t see why it matters whether we say that the balls are distinguishable or not, so long as we say that their locations are independent (and if we don’t say that, we can get any aswer we like that’s between zero to one). If someone asked for the probability of two heads when two fair coins were flipped, it wouldn’t make sense to ask whether the coins were distinguishable. And I though balls were fermions. On one level it changes the analysis. If they’re distinct, you must add this line of reasoning to your answer to justify throwing out the labels, or you must argue with the labels all the way through (giving rise to this n[sup]n[/sup] nonsense), though it will cancel out in the end. As for the balls being fermions, then you couldn’t have two in the same container at all and the probability for the OP would be 0. ---
**Author:** ![Josh\_dePlume](https://avatars.discourse-cdn.com/v4/letter/j/bbe5ce/32.png) [@Josh\_dePlume](https://boards.straightdope.com/u/Josh_dePlume)\ **Post date:** [August 13, 2004, 10:06pm UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/37 "2004-08-13T22:06:02Z")
> [@Mathochist](#): > > On one level it changes the analysis. If they’re distinct, you must add this line of reasoning to your answer to justify throwing out the labels, or you must argue with the labels all the way through (giving rise to this n[sup]n[/sup] nonsense), though it will cancel out in the end. As long as we agree that it will “cancel out in the end”. So the original question was not ambiguous, and n!n(n-1)!(n-1)/(2n-1)! cannot be claimed to be a valid answer. ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [August 14, 2004, 7:50am UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/38 "2004-08-14T07:50:34Z")
> [@Josh\_dePlume](#): > > As long as we agree that it will “cancel out in the end”. So the original question was not ambiguous, and n!n(n-1)!(n-1)/(2n-1)! cannot be claimed to be a valid answer. Um, I’d like to see the flaw in my argument pointed out. Just because it’s a different form doesn’t mean it’s not the same function. ---
**Author:** ![Josh\_dePlume](https://avatars.discourse-cdn.com/v4/letter/j/bbe5ce/32.png) [@Josh\_dePlume](https://boards.straightdope.com/u/Josh_dePlume)\ **Post date:** [August 14, 2004, 1:37pm UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/39 "2004-08-14T13:37:01Z")
> [@Mathochist](#): > > Um, I’d like to see the flaw in my argument pointed out. Just because it’s a different form doesn’t mean it’s not the same function. For n=2, n!n(n-1)!(n-1)/(2n-1)!=2/3, whereas n(n-1)n!/(2n^n)=1/2, so they are not different forms of the same function (as inspection will also show). The flaw is the assumption that all of the outcomes, not distinguishing beween balls, are equally probable, e.g., for n=2, that (2, 0), (1, 1), and (0, 2) each occur with probability 1/3, when the correct probabilities are 1/4, 1/2, and 1/4. ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [August 14, 2004, 4:37pm UTC](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443/40 "2004-08-14T16:37:07Z")
> [@Josh\_dePlume](#): > > For n=2, n!n(n-1)!(n-1)/(2n-1)!=2/3, whereas n(n-1)n!/(2n^n)=1/2, so they are not different forms of the same function (as inspection will also show). The flaw is the assumption that all of the outcomes, not distinguishing beween balls, are equally probable, e.g., for n=2, that (2, 0), (1, 1), and (0, 2) each occur with probability 1/3, when the correct probabilities are 1/4, 1/2, and 1/4. Yes, as had _already been settled_. > [@](#): > > As long as we agree that it will “cancel out in the end”. So the original question was not ambiguous, and n!n(n-1)!(n-1)/(2n-1)! cannot be claimed to be a valid answer. This phrasing (at least to me) has the semantics of “the invalidity of your response is connected to the purported ambiguity about the balls being distinct”. I’ll say again, as I _already admitted_, that my answer was wrong because of how I interpreted “equal probabilities”. Mea culpa, mea culpa, mea maxima culpa. If you want blood you’ll have to provide a mailing address. [Previous page](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443.md?page=1) [Next page](https://boards.straightdope.com/t/probability-n-balls-and-n-containers/259443.md?page=3)