Prove that the number of ways to put $n$ distinct balls into $n$ distinct boxes is $n^n$

Prove that the number of ways to put $n$ distinct balls into $n$ distinct boxes is $n^n$

The only approach I've come up with is to start with $1$ ball in each box, count the permutations, then take a ball out of one of the boxes and put it in another and then take the permutations times $n$ choose $2$ but then the process begins to branch and begins to feel intractable.

I find it surprising that the resulting formula, $n^n$, is so simple and that it's the same formula as order matters repetition allowed; is there a way to map this problem into that one?

• I think you require that the boxes be distinct. Otherwise, with $n=2$, the balls are either together, or separate, so there are only 2 ways and not 4. And if the boxes are distinct, use the rule of product. – Calvin Lin Jul 6 '13 at 0:31

1 Answer

We assume that the boxes are also distinguishable.

Where shall the ball with label $1$ go? We can put it into any of the boxes, so we have $n$ choices.

For each way of choosing where Ball $1$ goes, there are $n$ ways to decide where the ball with label $2$ goes.

So there are $n^2$ ways to decide the fates of Ball $1$ and Ball $2$.

For every way to decide where Ball $1$ and Ball $2$ go, there are $n$ ways to decide where Ball $3$ goes.

And so on.

Remark: More generally, suppose that we have $n$ balls and $k$ boxes. At each stage, we have $k$ possible decisions, for a total of $k^n$.

It is easiest to answer your second question in this more general setting. Imagine we have an alphabet of $k$ letters, and we want to make an $n$-letter word, repetition allowed. There are $k^n$ ways to do this. The mapping is as follows.

Suppose that we have a word of length $n$. Examine it, letter by letter. If the $i$-th letter of the word is the "letter" $j$, put the $i$-th ball into Box $j$. This establishes a bijection between words of length $n$ and ways to put balls into boxes.

• This assumes that the boxes are distinct. If the boxes are indistinguishable, this won't work. – Calvin Lin Jul 6 '13 at 0:43
• @CalvinLin: Thanks, I have made the assumption clear at the beginning. Didn't think of it because the stated answer is the answer for distinguishable boxes. – André Nicolas Jul 6 '13 at 0:48
• @CalvinLin Calvin I 've been looking up these questions and I am confused in this question(where you have commented) and result of star and bars. Could you tell me what the difference between both these problems?math.stackexchange.com/questions/192670/… – Daman Aug 22 '18 at 19:26
• The balls are distinct or indistinct. (And in some other cases, check if the buckets are distinct/indistinct.) – Calvin Lin Aug 24 '18 at 1:49