# Sample Space: Why Assume Repetition? – n balls into n cells

combinatoricsprobability

The answer to the question has been given here before: $$n\choose 2\frac{n!}{n^n}$$

But my question is why is the sample space considered $$n^n$$?

Isn't this technically assuming repetition of the balls into each cell (something not possible by the nature of the question)?

I would think a permutation(n,n) would be the correct approach instead.

Where am I going wrong in my thinking?

For those who have yet to come across the question:
"If n balls are placed at random into n cells, find the probability that exactly one cell remains empty."

I believe substituting two different variables will help you to grasp the mechanics of this problem. So let there be $$k$$ balls and $$n$$ cells. This should be much more clear when there are not $$n$$ of each. When $$k=n$$ and one cell is left empty, then clearly repetition is key to solving the problem; if there could be no repetition then it would be impossible for any cell to remain empty for the case where $$k=n$$. Let's look at the case where $$k < n$$. Supposing $$k=5$$ and $$n=7$$. Each of the five balls, each distinct (all of different colors), can be placed in a cell in seven ways, and each cell is distinct since the cells are arranged in an order. A ball can be placed in a cell that already has a ball in it, so there is repetition and the placement of one ball does not affect the placement of the ones that follow. So the number of ways of placing the five balls in seven cells is $$7\times7\times7\times7\times7 = 7^5$$. Note that if repetition were allowed, the first cell could be chosen n=7 ways while the second cell could be chosen n-1=6 ways etc. Now let's suppose $$k > n$$. Supposing $$k = 5$$ still but now $$n = 4$$. Each of the five balls can be placed in a cell in four ways. It has to be possible to place a ball in a cell that already has a ball in it, or else we would run out of cells. Each ball is distinct so it isn't the same to put the blue ball in the second cell as it is to put the green ball in the second cell. So the number of ways of placing the five balls in four cells is $$4\times4\times4\times4\times4 = 4^5$$. The general formula for the total number of possible arrangements of $$k$$ distinct balls in $$n$$ distinct cells is $$k^n$$. When $$k = n$$ then the total number of possible arrangements could be written as $$n^n$$. Now you can change the assumptions, for instance, so that the balls are not distinct but are all of the same color, and update the resulting outcomes.