Q: If N balls are placed at random into N cells, find the probability that
exactly one cell remains empty.
The book says N!(N[N-1]) / 2[N to the Nth power]
Is this a mistake? I don’t see how that 2 got there.
My analysis: the total number of ways to put N balls in N cells is [N to the Nth power]. That explains the second factor in the denominator.
The other terms are determined by how many ways one can put the N balls in N cells with exactly one empty. This can be done by a sequence of independent choices:
Decide which cell will be empty. There are N choices here.
Arrange the N balls in order in N! ways.
For a given arrangement of the balls, drop the first N-1 balls in the N-1 cells that are to be filled, from left to right. This can be done in one way only.
Decide where to put the last ball. This can be done in N-1 ways.
Multiplying the four numbers obtained in the above steps, we get N[N-1]N!
So that my numerator agrees with the book’s. But the 2 in the denominator is a mystery to me.
Bottom line: Is that 2 in the denominator a mistake? If not, what have I missed?
I usually use a quick reality check. Take N = 2, and try to falsify the formula.
Assuming order of balls in cells is not significant and balls are distinguishable, there are 4 ways to put 2 balls in 2 cells, and 2 ways to do that so that (exactly) one cell is empty. Probability (assuming the usual methodology) is 2/4 = 0.5. The formula gives 2!(21)/2/2^2=0.5. So I guess you cannot drop that 2 (of course this does not prove the formula, it just disproves the modified formula).
Hint: your procedure arrives at every distribution having two balls in some cell in two ways: once putting the first ball during step 3, and the second ball during step 4, and the second time vice versa. You want to ignore the order of balls in cells, thus divide by 2.
Smiling Dave, are you sure that’s correct? Multiplying [N-2]! with N[N-1]/2 will give you N!/2. I think you were initialy along the right lines but missing one step. First the boxes are all different, and hence can be ordered in N! ways. The N(N-1) term follows from the fact, as you noted above of the number of ways of selecting one ball out of N, and subsequently 1 ball out of N-1. The 1/2 factor is a result of the fact that ordering doesn’t matter in placing the balls(or analogously in “removing them”). Hence if I have 3 balls; A, B and C I can remove 1 in 3 ways. I can then take 1 of the remaining 2 and add it to the one removed in 2 ways. This gives me 6 arrangements: AB, AC, BA, BC, CA and CB. Clearly half of these are “degenerate”(equivalent to each other) since ordering of the pair is not deemed to matter. Hence generalising to picking a pair out of N balls out of we get N(N-1)/2 a special case of the binomial coefficient you’ve mentioned above N!/(N-r)!r!. Hence the number of ways of arrangign the balls and the boxes is N!N(N-1)/2 and the probabillity of this outcome is of course the same multiplied by (1/N)^N, since we assume even probabilities of being in each box at random.
(BTW I haven’t forgotten our discussion on utility. I will get back to you eventually, just please forgive me if it’s not that forcoming!)
But my second method is correct as well. The numerator has an N[N-1] factor twice. Once from steps one and two combined, and once from step three. So indeed one instance of N[N-1] combines with [N-2]! to form N!, as you pointed out, but there is another instance as well.