blackpenredpen

math for fun 

To see this working, head to your live site.
  • Categories
  • All Posts
  • My Posts
Flamitique 78
Apr 28, 2021

Combinatory problem

in Math Problems

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 !

1 answer0 replies
0
0
Ian Fowler
Apr 28, 2021  ·  Edited: Apr 29, 2021

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




1 comments