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 for each of those 3 choices we have 3 choices for ball2. That's why we multiply 3x3 to get 9 different ways for the first 2 balls.
==========================================================
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 generate 3 different ways of 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