3
$\begingroup$

I have been practicing a bunch of combination and permutation problems and I think I have some misunderstandings about how to approach these types of problems.

For example,

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

For this question, I thought it this way:

First, we have n cells for n balls: $n^n$ Then one cell must have 2 balls:${n \choose 2}$ and now we are placing $(n-2)$ balls into $(n-2)$ cells: $(n-2)^{(n-2)}$ Thus, $\frac{{n \choose 2}(n-2)^{(n-2)} }{n^n}$

And this was wrong, the "right" way of thinking through this question was:

$n$ ways to choose empty cell, $n-1$ ways to find cell with two balls, and then select 2balls that goes into the same cell, ${n \choose 2}$ and finally arrange remaining $n-2$ cells, $(n-2)!$

Thus, $\frac{n*n-1*{n \choose 2}*(n-2)!}{n^n}$ = $\frac{{n \choose 2} * n!}{n^n}$

I don't understand why my way of solving this problem is wrong. What am I missing?

Second example

In the game of dominoes, each piece is marked with two numbers. The pieces are symmetrical so that the number pair is not ordered (so for example, (2,6)=(6,2)). How many different pieces can be formed using the numbers 1, 2,...,n?

I thought for the two numbers (F,B) we can select $n$ numbers. We have $n$ numbers to choose to put it on the front and $n$ numbers to choose for the back. So my answer was $n^n$ different pieces can be formed.

However, the correct way of thinking is that you choose 2 from n: ${n \choose 2}$ and $n$ ways to have repeats like (2,2),(3,3). Thus, ${n \choose 2}+n$

For these types of questions, I really can't come up with the "right" way of thinking unless I see the answer. Could anyone point out what I am doing wrong? Thank you!

$\endgroup$
3
  • 2
    $\begingroup$ Just an advice: to get hold on "the right way of thinking" solve the question for small $n$ by brute force. If you have a non-matching answer allready then find the smallest non-matching $n$ to take a closer look. $\endgroup$
    – drhab
    May 5 '17 at 8:40
  • $\begingroup$ The $(n-2)^{(n-2)}$ (for $(n-2)$ balls in $(n-2)$ cells) includes the possibility that all the remaining balls are placed in the same cell. However, there is only one cell allowed to be empty. Also, you only consider one particular cell to be empty and only one particular cell to have $2$ balls, even though you have choices for these. You are really computing the probability that the first cell has no ball and the second has two. Except of course, for the typo in the denominator (it schould be $n^n$ I believe). $\endgroup$ May 5 '17 at 8:45
  • $\begingroup$ @MatthiasKlupsch Okay. I see what you are saying. Also I fixed the typo. Thank you. However, I am still confused. Like the right way of solving the problem, first it counts the number of ways to choose cells then considers the way to select "balls" and then deals with the remaining cells. What is this inconsistency? I feel like I should choose one, let's say "cells", and think of what is happening to the cells. It is confusing to me how you can arbitrarily choose what to consider and put everything in the numerator. $\endgroup$
    – johnson75
    May 5 '17 at 8:54
1
$\begingroup$

For the first one, you are counting the ways where the first cell contains exactly two balls. This is not at all the same thing as having exactly one cell empty.

You can modify your solution as follows. First we count the number of ways where the first cell has two balls, and exactly one is empty. There are $\binom n2$ ways to choose the balls for the first cell. Now we have $n-2$ other balls to arrange into the other $n-1$ cells, but they must all be in different cells. We can think of this as permuting $n-1$ things ($n-2$ balls and one empty cell), which can be done in $(n-1)!$ ways. So there are $\binom n2(n-1)!$ ways to have exactly one empty and two in the first. There are the same number of ways with two in the second, third, etc, so in total there are $n\binom n2(n-1)!$.

For the second, the main issue is that if there are $n$ choices for the front and $n$ for the back, that is $n\times n$, not $n^n$, in total. However, $n^2$ isn't the right answer either, because you have counted most of the options twice: 1 on front and 2 on back is the same as 2 on the front and 1 on the back, but you've counted them separately. In fact, the only options you haven't counted twice are the doubles. There are $n$ doubles, and you have counted $n^2-n$ non-doubles, but you've counted them twice so there are actually $\frac{n^2-n}2$ non-doubles. So the total is $n+\frac{n^2-n}2$.

$\endgroup$

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.