3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Calvin Lin Jul 6 '13 at 0:31
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This assumes that the boxes are distinct. If the boxes are indistinguishable, this won't work. $\endgroup$ – Calvin Lin Jul 6 '13 at 0:43
  • $\begingroup$ @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. $\endgroup$ – André Nicolas Jul 6 '13 at 0:48
  • $\begingroup$ @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/… $\endgroup$ – Daman Aug 22 '18 at 19:26
  • $\begingroup$ The balls are distinct or indistinct. (And in some other cases, check if the buckets are distinct/indistinct.) $\endgroup$ – Calvin Lin Aug 24 '18 at 1:49

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.