4
$\begingroup$

I'm working on example 1.18 in Casella & Berger and I'm confused by the solution.

The problem states:

If n balls are placed at random into n cells, find the probability that exactly one cell remains empty.

In the solutions manual, it states that there are $n^n$ total ways to place $n$ balls into $n$ cells. This implies the sampling method is ordered with replacement. I agree that the $n$ cells are sampled with replacement. But, why is it considered ordered?

My logic:

Let's pretend there are 3 cells. If I place a ball into {1,1,2}, {1,2,1}, or {2,1,1}, in the end I have 2 balls in cell 1, and 1 ball in cell 2. The ordering does not matter.

What am I misunderstanding here?

Improve this question
$\endgroup$
7
  • $\begingroup$ You should add the self study tag. I don't see where ordering is mentioned. There is ordering in the sense that two or more outcome that are identical except for order count multiple times because of ordering differences. Find all the ways the first cell can be empty multiply that by n and divide by $n^n$. So in the case of three ball you have (0,1,2) and (0,2,1). Now the 0 can occur in any of the 3 places. So multiply by 3 and then divide by $3^3$ to get 6./27 =2/9.. $\endgroup$
    – Michael R. Chernick
    May 10, 2018 at 3:19
  • $\begingroup$ @MichaelChernick the ordering comes into play by the notion that there are $n^n$ ways to arrange n balls into n cells. This implies ordering. If it were unordered, the number of arrangements would be $\binom{n+r-1}{r}$. $\endgroup$
    – ZachTurn
    May 10, 2018 at 13:03
  • 1
    $\begingroup$ The events {1,1,2}, {1,2,1}, or {2,1,1} are easy to use (when counting) because they all have equal probability to occur. Events like 'in the end I have...' are not. $\endgroup$
    – Sextus Empiricus
    May 10, 2018 at 13:06
  • 1
    $\begingroup$ If every elementary event has equal probability to occur, then the probability for a certain event X is the number of the elementary events that lead to that event X divided by the total number of elementary events. $\endgroup$
    – Sextus Empiricus
    May 10, 2018 at 13:17
  • 1
    $\begingroup$ I guess what I meant to say is that all orderings are counted. $\endgroup$
    – Michael R. Chernick
    May 10, 2018 at 14:02

1 Answer 1

Reset to default
4
$\begingroup$

Since this problem is self study (and the solution is given in the text) I'll sketch out how I would approach the problem and let you fill in the gaps. I think it's easiest to approach by counting the valid orderings (like Michael suggested in the comments) and dividing by the total possible orderings.

The problem becomes easier when you think about what must be true if only one cell is empty. Here's a hint: if precisely one cell is empty, can a cell have 3 balls in it?

Solution hidden below:

No. If precisely 1 cell is empty, then precisely 1 other cell has 2 balls in it and the rest have 1 ball. If one cell had 3 balls then at least 2 cells must be empty.

Given that, it's straightforward to count the number of valid events and total events.

How many ways can we choose the 2 cells which don't have 1 ball in them?

${n}\choose{2}$

How many ways can we order the balls and place them into cells?

$n!$

That gives us our numerator, the total number of possible orderings:

${{n}\choose{2}} \cdot n!$

How many ways can I place $n$ balls into $n$ cells? Well the first ball can be placed into $n$ cells, the second into $n$ cells, and so on leading to $n^n$ total possible arrangements of the system. This gives the probability as (number valid)/(total):

${{n}\choose{2}}\ n!\ /\ n^n$

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ +1 but, with a different interpretation of the steps I get to a similar result (a factor 2 moves from one term to the other). "the 2 cells which don't have 1 ball in them" these are different cells, one of them has 0 balls and the other has 2 balls. So I would use $P(n,2)$ instead of $C(n,2)$ for "How many ways can we choose the 2 cells which don't have 1 ball in them?". The factor 2 difference is 'recovered' when considering "How many ways can we order the balls and place them into cells?" as 'How many ways can we order the filling of n-1 cells by n balls" which is $\frac{n!}{2!}$. $\endgroup$
    – Sextus Empiricus
    May 11, 2018 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.