Hi ! I need help on a question that I'm stuck with, and I have no idea how to prove the result ^^' It would really help me if you guys could show me how to solve it :D

So, there is the question :

Let n be a natural number greater than 0.

We have in our possesion n balls, numbered from 1 to n.

We place them randomly in a box that has n spots, and we can put between 0 and n balls in each spot.

How many ways to put all the balls in this box exist ?

I know the answer is n^n, but I have no idea of how to prove it...

Thanks !

Try and think of it this way.

Place the first ball - you have n choices

Now when you place the second ball you still have n choices as there is no restriction on the number of balls in each box.

For example if n = 3 balls. Let's place only balls 1 and 2 and we will not place ball 3.

So for the ball1 you have 3 choices and

we have 3 choices for ball2. That's why wefor each of those 3 choicesdifferent ways for the first 2 balls.multiply 3x3 to get 9==========================================================

Place ball1 (3 choices)box1 box2 box3

1 -- --

-- 1 --

-- -- 1

===========================================

Now place ball 2. Here are all 9 ways.These are the 3 ways from green above - box1 has ball1. Note that ball 2 has 3 spots

box1 box2 box3

1 2 --

1 -- 2

1,2 -- --

These are the 3 ways from orange above - box2 has ball1. Again ball2 has 3 spots.

box1 box2 box3

2 1 --

-- 1 2

-- 1,2 --

These are the 3 ways from yellow above - box3 has ball1. Again ball2 has 3 spots.

box1 box2 box3

-- 2 1

2 -- 1

-- -- 1,2

Now we have to place ball3.I'm not going to write them all out, so you are going to have to imagine that for

each of the 9 lines in the ball2 section(3G,3O,2Y) you will generate3 different waysof placing ball3 giving us a total of 9x3 = 27 ways.The green line 1,2,-- will give us (13,2,--) (1,23,--) (1,2,3)

Repeat 8 more times

So we have 3^3 ways of placing the 3 balls into the 3 boxes.

So for each of the n balls we have n choices for each ball ====> n*n*n*n*...*n (n times) = n^n