2
$\begingroup$

Find the probability that exactly one cell is empty.

I have found a lot of similar questions online but I am still confused with the derivation of the final answer, which is :

$$\frac{(n)(n-1)\binom{n}{2}(n-2)!}{n^n}$$

The first question is, when we find the denominator, all we have thought about is the ordering of $n $ distinct balls. However, when it comes to the numerator, $n*(n-1)$ is actually derived from ordering the empty and the two balls cell; and then multiply it with the number of ways in which we could have placed the two balls into the same cell... (which is the combination, again) Then multiply it with the ordering of the remaining $n-2 $ balls...

It's really confusing that we seem to mix the combination and permutation at the same time. I don't really understand how this multiplication work. For example, why don't we need to multiply $\binom{n}{2}$ with 2? For example, if we pick up ball $1 $ and ball $3$ to be in the same cell, similarly we could pick up ball $3 $ and ball $1$. Even though they may deliver the same result but they count twice instead of once.

$\endgroup$
2
$\begingroup$

To answer your actual question in the last paragraph: If you have two distinct balls and one cell, what's the probability that both balls are in the one cell? The way you're suggesting to count, the probability would be $2$, since there are two different orders in which you can put the balls into the $1$ cell, and just $1^2=1$ in the denominator. The denominator doesn't count an ordering, as you write; it counts the number of possible assignments of $n$ (distinct, labeled) balls to $n$ cells, without regard to how the assignments come about, and thus in particular to the order in which the balls are placed in the cells.

As regards an interpretation of the correct count, two answers have already been given, here's another one:

The result simplifies to $\frac{n!\binom n2}{n^n}$. Label the $n$ balls and the $n$ cells with the numbers $1$ through $n$. Assign the balls to the cells according to one of $n!$ permutations. Then choose $2$ cells and move the ball with the lower number into the other cell. This constructs each admissible assignment in exactly one way, so there are $n!\binom n2$ admissible assignments.

$\endgroup$
  • 1
    $\begingroup$ Thank you so much! It's by far the most straightforward interpretation I have encountered! $\endgroup$ – Chloe Zhou Sep 12 '18 at 13:53
0
$\begingroup$

$n^n$ denotes the total number of ways to put n balls into n cells.

$n$ denotes the number of ways to choose the empty cell

$n-1$ denotes the number of ways to choose the cell with $2$ balls.

$\binom n2$ denotes the number of ways to choose 2 balls from n balls.

$(n-2)!$ denotes the number of ways to choose n-2 balls into the rest of the cells.

$\endgroup$
0
$\begingroup$

Think of it as nC2 (n-2)! = n! / 2

Once you exclude the hole and double you pick a slot one at a time. 1st slot you have n balls to choose. 2nd slot n-1. Etc. As 2 slots are excluded the factorial ends before it gets to 2, hence the divide by 2.

$\endgroup$
  • 1
    $\begingroup$ Please read this MathJax tutorial, which explains how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Sep 12 '18 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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