balls in bins v2

Balls in Bins (Version 2) PhL 6.2.15 heavily updated 10.13.16 When I last did this on 3/5/2003, I failed to follow through and state the general results, so I am doing that now since I simply would like to have the results written down somewhere. 1. N labeled balls in B boxes // labeled ≡ distinguishable 1 2. N identical balls in B boxes // identical ≡ indistinguishable 2 2a. What happens if B >> N ? 3 3. Multiple sets of boxes with labeled balls (Bose) 3 4. Multiple sets of boxes with identical balls (Bose) 6 5. Multiple sets of boxes with labeled balls (Fermi) 7 6. Multiple sets of boxes with identical balls (Fermi) 8 6. Summary of Way counts for our four cases: 9 7. Comparison with other sources: 10 Appendix A. Ways to configure N labeled balls into a specific {Ni} ordered partition? 11 Appendix B. Ways to configure N labeled balls into a specific {Ni} non-ordered partition? 12 N = number of balls (particles) B = number of boxes (states at a given energy level, the states are distinguishable) 1. N labeled balls in B boxes // labeled ≡ distinguishable Suppose you have N distinguishable (say by color) balls and B bins in which to put them. You take the first ball and flip it into one of the B bins, so B ways. You keep doing this and there are then B*B*...*B = BN ways to put those N balls into the B bins. That is the complete answer to this problem. ways = BN Example: B = 2 balls (R=red, G=green), N = 3 bins. Here is a list of the NB = 32 = 9 ways: 1 RG 2 R G 3 R G 4 G R 5 G R 6 RG 7 R G 8 G R 9 RG 2. N identical balls in B boxes // identical ≡ indistinguishable If the balls are indistinguishable, a different method of solution is needed. You could start with the answer to problem 1 and then correct for overcounting in each partition case, but it is a large mess involving sets of factorials For example, if you have B = 3 bins and you get this situation shown on the left for N = 5 balls, then you have to divide by 2! twice. But for the situation on the right, you divide by 3! once. This method probably leads to some kind of addition theorem. Somewhere I figured this out long ago. The better method is to think of the B bins being separated by W = B-1 "walls". You have a little kit in front of you which consists of W = B-1 walls (wall = | ) and N balls (ball = *). So you have B-1+N little toys in your playbox. You imagine then B-1+N little places to put things in a line. For N = 5 balls and B = 4 boxes, we have then N = 5 balls and W = 3 walls, so total of 8 toys to lay out. Here is one way to lay them out * | * * | | * * The balls are identical AND the walls are identical. So the total number of layouts in this case is ways = 8! / (5! 3!) = (8,3) = (8,5) You have your row of B-1+N places on the table. The number of ways to pick a committee of 3 walls from the 8 positions is the number of layouts. This is the same as the number of ways to pick a committee of 5 balls from 8 positions on the table. So here is the general solution: Number of ways to place N indistinguishable balls in B boxes = (B-1+N,N) = (B-1+N,B-1) ways = = = // both forms are the same Example: B = 2 balls in N = 3 boxes. Both balls are green. ways = (4,2) = 4x3x2/(2x2) = 6 : 1 GG 2 G G 3 G G 6 GG 7 G G 9 GG Since you can put any number of balls in a box, this is called Bose-Einstein statistics if the boxes are states into which you can put particles. 2a. What happens if B >> N ? In this case, the numerator factorial is (N+B-1)! but since B >> N >> 1, this is roughly just B! With this gross approximation, you get ways = 1/N! which is the wrong answer. This is just the N = 0 case. A more accurate thing to do would be to write out the numerator (N+B-1)! as (B-1+N)(B-1+[N-1])(B-1+[N-2]) .....(B-1+1)(B-1)! = there are N factors here before (B-1)! Then you have cancellation of the (B-1)! factors top and bottom and you get ways = = = Now assume B >> N, and then each numerator factor is just B, so you end up with ways = This is the situation which arises in the blackbody Boltzmann world! Here is the way Zemansky explains this result on page 253-254: If B >> N, then the chance of having more than one ball in any box are miniscule. So you layout your B boxes in a row and you put in your balls. For example Here we put N = 3 balls into a large number B of boxes. The ways to do this for distinguishable balls is going to be BN as shown in part 1 above. But then you have an overcount factor of N! which is 3! for the case drawn above. This then gives the same ways = result. While we're at it, let's do another limit with N << B : = = → // N factors up top 3. Multiple sets of boxes with labeled balls (Bose) I keep getting confused by having no picture, so I will use an energy level type picture to show the idea of multiple sets of boxes. For example ε1 ___ ___ ___ B1 = 3 this line is one "big box" N1 ε2 ___ ___ B2 = 2 this line is one "big box" N2 The underlines represent "little boxes" where I have installed 5 labeled balls where N1 = 2 and N2 = 3 : ε1 ab φ φ ε2 c de This is a particular microstate for this m = 2 system where the 5 balls are abcde. The balls a and b are in the same "state" exactly. Within a particular state, ordering does not matter. So the following microstate is exactly the same as the above one : ε1 ba φ φ ε2 c de The states on a horizontal line ARE different even though they have the same energy. They have different quantum numbers like 1/2,1/2 and 1/2,-1/2 for spin states. Now let's switch to a simpler example: ε1 ___ ___ B1 = 2 this line is one "big box" N1 = 2 ε2 ___ ___ B2 = 2 this line is one "big box" N2 = 2 I will now list off 4 different microstates for four labeled particles abcd : ε1 ab φ ε2 cd φ ε1 a b ε2 cd φ ε1 b a ε2 cd φ ε1 φ ab ε2 cd φ Again, within a state ordering does not matter, so for example ab = ba. A denser notation for the above list is the following where I put the ε1 states on the left and the ε2 ones on the right: ε1 ε2 ab,φ cd,φ a,b cd,φ b,a cd,φ φ,ab cd,φ The number of states in the left column can be written simply as B1N1 since we each of the N1 balls has B1 places it can go. I could enumerate three more groups like the above group of 4 microstates by varying the ε2 column. In this way, it seems that there are 16 different microstates. Let's just show them all for this one simple example: ε1 ε2 ab,φ cd,φ a,b cd,φ b,a cd,φ φ,ab cd,φ ab,φ c,d a,b c,d b,a c,d φ,ab c,d ab,φ d,c a,b d,c b,a d,c φ,ab d,c ab,φ φ,cd a,b φ,cd b,a φ,cd φ,ab φ,cd Now the 16 is a special case of B1NB2N which here is 2222 = 16. All these 16 states have a and b in the ε1 level. All these states can be associated with the unordered partition {ab,cd} of the N=4 balls where the left side refers to the ε1 world and the right to ε2 world. In Appendix B below I show that the general formula for the number of unordered partitions for a set {Ni} is this, where balls are labeled, ways = In our example, we have ways = = 6 We can identify those six ways as follows, {ab,cd} {ac,bd} {ad,bc} {bc,ad} {bd,ac} {cd,ab} Notice that {ab,cd} and {cd,ab} are different ways because the ε1 and ε2 are different energy levels. So in our example with labeled balls there are 6 * 16 = 96 different microstates. The general formula is this labeled-ball microstates = [ B1NB2N .... BmN ] where the first factor is the number of ways to partition N labeled particles into unordered partitions {Ni}. The second factor [..] is the number of ways each of these unordered partitions can be "installed" into the little boxes, and we are Bose in that any number of balls can be in a box. We have shown : Theorem 1: Suppose we have N labeled balls and we have m different energy level states and the degeneracy of the state with εi is given by Bi. If we restrict our interest to a particular set of partition count integers {Ni}, then the total number of distinct ways the balls can be loaded into the energy diagram (with N1 in level ε1 etc) is this: ways = [ B1NB2N .... BmN ] = N! .... 4. Multiple sets of boxes with identical balls (Bose) As shown at the very end of Appendix B, in this case there is only 1 way to make a partition of N balls with counts {Ni}. Meanwhile, within the 1-group, we know from 2 above that the number of different microstates for the 1-group is this and similarly for the other groups. We end up with the following theorem : Theorem 2: Suppose we have N identical balls and we have m different energy level states and the degeneracy of the state with εi is given by Bi. If we restrict our interest to a particular set of partition count integers {Ni}, then the total number of distinct ways the balls can be loaded into the energy diagram (with N1 in level ε1 etc) is this: ways = 1 * ...... = Πi=1m = Πi=1m This result agrees with the following web clip, and since we allow more than 1 particle in a box, we are talking Bose-Einstein. If it happens that Bi >> Ni for all i values, we know from (2a) that the above becomes ways = 1 * .... This result is similar to the Theorem 1 result but there is no N! overall factor. 5. Multiple sets of boxes with labeled balls (Fermi) In the Bose case where any number of labeled balls can go into a state, our count-of-partitions factor was while each group got a factor BiN where this last is the number of ways you can put Ni particles into Bi boxes with no restriction on number of balls in a box. In the labeled-balls Fermi case we have the same factor as the number of ways to make the initial partition into count set {Ni}. Since we are now in the Fermi world, if there are Bi energy levels at εi , the count Ni is restricted to be Ni ≤ Bi. We can now have at most one ball in a box. So we now assume that the partition count set {Ni} meets this requirement. So consider putting N balls in B boxes with Fermi rules and labeled balls. Take the first ball. There are B places you can put this ball. The second ball can go B-1 places. So N factors here ways = B(B-1)(B-2)....(B-[N-1]) = = N! Combining these factors for each group we then get ways = [ N1! ] [ N2! ] .......[ Nm! ] = N! .... and then we have: Theorem 3: Suppose we have N labeled Fermi balls and we have m different energy level states and the degeneracy of the state with εi is given by Bi. If we restrict our interest to a particular set of partition count integers {Ni} which is Fermi-legal, then the total number of distinct ways the balls can be loaded into the energy diagram (with N1 in level ε1 etc) is this: ways = N! .... 6. Multiple sets of boxes with identical balls (Fermi) In this case the initial factor is replaced by 1 as noted earlier. Now for each group the number of ways is just the number of ways if picking a committee of N boxes from B boxes and for each such committee we have a "way". So the result here is ways = 1 * .... and interestingly this is the same as the result for labeled particles but without the overall N! factor! Theorem 4: Suppose we have N identical Fermi balls and we have m different energy level states and the degeneracy of the state with εi is given by Bi. If we restrict our interest to a particular set of partition count integers {Ni} which is Fermi-legal, then the total number of distinct ways the balls can be loaded into the energy diagram (with N1 in level ε1 etc) is this: ways = .... = Πi=1m This result agrees with the following web clip, and since we allow at most 1 particle in a box, we are talking Fermi-Dirac statistics. 6. Summary of Way counts for our four cases: Bose Fermi labeled N! .... 1 N! .... 3 identical Πi=1m 2 .... 4 = Πi=1m = Πi=1m And in the limit N << B, Bose N << B Fermi N<< B labeled N! .... 1' N! .... 3' identical .... 2' .... 4' 7. Comparison with other sources: Zemansky page 255 (10.4) gives the result 2' shown above. He is in the N << B limit, and he has identical balls which are gas molecules. This is also the result I use in Lagrange doc. Also, in problem 10-5 on page 273 Zemansky has our result 1' for labeled particles! Also, in problem 10-6 on page 273 Zemansky has our result 2 for labeled particles but he has reduced either gi or Ni by 1 to make the formula simpler and he calls it ΩBE. Also, in problem 10.7 on page 273 Zemansky has our Fermi result 4 for labeled particles! Reif: I can find nothing on this topic in the fat brown book. He says a lot on the subject circa p 351, but there is never any count of microstates. Wait! On page 343 bottom I see a result for labeled particles and it is assumed that each state has degeneracy 1. This is my result 1 above with all Bi = 1. Fine. Degeneracy shows no interesting hits in his appendix. Neither Reif book has anything. Sears: book of Jim, has only same thing as Reif which is not much. Livesey: Page 13 [2.2.3] as the same result as Reif and Sears. On the next page he does my Lagrange Multiplier analysis in this simple case of no degeneracy. wiki: https://en.wikipedia.org/wiki/Maxwell%E2%80%93Boltzmann_statistics This page has various of my results. First we get this result The author is talking about labeled particles (that name same properties) and this is the number of ways of getting non-ordered partitions from N particles, and agrees then with my Appendix B result. He has my same thing At this point each level has degeneracy 1, so this is then my result 1 from the summary above. Adding degeneracy, the wiki author then gets my result 1 more fully, again labeled and Bose particles, Then without proof, the author says that if the particles are identical, you get instead which then matches my result 2. Somehow the identicalness solves the "Gibbs paradox" which I don't care about right now. Without identicalness, you get the wrong partition function and the wrong expression for entropy S which is not "extensive", see Reif. Finally, we get this result in our usual limit which is my result 2' for identical and Bose. Finally, the author does exactly my Lagrange Multiplier example. So that page has a lot of stuff on it! Appendix A. Ways to configure N labeled balls into a specific {Ni} ordered partition? Imagine now that we have m large boxes and we want to get N1 in the first, N2 in the second and so on. These larger boxes are the sums of the smaller boxes shown above. Here we are talking about ordered partitions. For example, these ordered partitions are different: ab cd and ba cd. In how many ways can you pick a subset of N1 balls from a larger set of N balls? Well, you start by picking one of the N balls and you put it in your subset. There are N ways to do that. There are then N-1 choices for the second ball, so there are N(N-1) ways to put the first two balls into the first set. Notice a might have been one of the N balls, and b might have been one of the (N-1) balls, but a↔b is counted as a separate case. When you are done, there are N(N-1)(N-2).....(N-[N1-1]) ways to fill up the first set. We have just selected the N1 balls, we have not installed them into the small boxes that make up the first set. Now we turn to the second set. We have N-N1 balls left in our ball supply bag. We repeat the above logic for the set of N2 balls and we find that there are then {N-N1}({N-N1}-1)({N-N1}-2).....({N-N1}-[N2-1]) ways to select N2 balls from those we have left. Now for each way of dealing with the N1 set, we have all these ways of dealing with the N2 set. So the total ways of handling N1 and N2 is the product of the above products, and that product is N(N-1)(N-2).....(N-[N1+N2-1]). We continue in this manner. When we are done, we have the product of m products, and that product is then N(N-1)(N-2).....(N-[N1+N2 + ....+Nm-1]) = N(N-1)(N-2).....(N-[N-1]) = N(N-1)(N-2).....(1) = N! So the final result is very simple and it is independent of the specific Ni values. Example: Let B1 = 2 and B2 = 2 and N1 = 2 and N2= 2 and balls are named abcd. There are 4! = 12 ordered partitions possible and here they are : ab cd ac bd ad bc ba cd ca bd da bc ab dc ac db ad cb ba dc ca db da cb Here is an alternate argument for N!. Suppose we have a bag of N balls and we are going to select the balls out of the bag one at a time and just put them in a row on a table, left to right. There are then N! ways to create this row of N balls on the table. The balls are distinguishable at this point, each ball has a number from 1 to N, and each of your row ways is different. We could then draw partition lines on the table at any locations we want and that would determine the {Ni}. But the total ways to make the rows is the same no matter where you draw those lines, and that is why the result N! is independent of the specific Ni values you use. In the above example, first entry is then abcd and there are a total of 12 ways to orient this list. If the balls were identical, all the resulting rows would be the same "way", so you would divide the result by N! and get ways = N!/N! = 1, and then there is only one possible way to make a row of balls on the table. In the above example that one way would be ** ** . Appendix B. Ways to configure N labeled balls into a specific {Ni} non-ordered partition? Start with (N,N1) as the number of ways to select the first partition (non-ordered partition). We are not saying the particles are identical, we are just saying that we are doing a non-ordered partition. For each of these (N,N1) ways there are then (N-N1,N2) ways to select the second partition. You pick a committee of N2 balls from the N-N1 balls you had after doing the first partition. So we end up with (N,N1) * (N-N1,N2) * (N-N1-N2,N3) * ... * (N-N1-N2 - ... - Nm-1,Nm) The last factor is really just (Nm,Nm) = 1. When you have done all the other partitions, you are left with Nm balls and there is only one way to select a committee of Nm balls from this set. You are done. Now write out the above product ...... We can cancel factors in adjacent terms to get = An alternate derivation is this: Start with the N! result of (2c) which counts both ab cd and ba cd where we are dealing with ordered partitions. If the order in each Ni group does not matter, we have overcounted by Ni! and then the result above is the number of ways to create the unordered partition {Ni}. Note that the particles are still distinguishable, it's just that we don't care how they are ordered within each Ni part of the partition. So now ab cd and ba cd are the same "way" in this new count. Example: Let B1 = 2 and B2 = 2 and N1 = 2 and N2= 2 and balls are named abcd. Here are the possible non-ordered partitions: ab cd ac bd ad bc bc ad bd ac cd ab There are only 6 possible non-ordered partitions. The formula says 4!/(2! 2!) = 3! = 6. Notice that we do not equate the items ab cd and cd ab. We think of the N1 and N2 groups as different groups, perhaps different energy levels. Suppose the balls are identical. How is the above discussion different? Recall that for non-identicals we said that the first number of ways was (N,N1) and the second (N-N1,N2) and so on. If the particles are identical, then we replace (N,N1) by 1 and (N-N1,N2) by 1 as well. The reason is this: line up the N identical balls. Pick the first N1 for the first group (one way), the next N2 for the second group (one way) and so on. There is only one way to do each of these actions. Another way to say it: lay the N identical balls in a row. How many ways can you install the dividers to get N1 and N2 and on to Nm ? Answer: exactly one way. Example: Let B1 = 2 and B2 = 2 and N1 = 2 and N2= 2 and balls are named aaaa. There is only one non-ordered partition which is aa aa .