wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Balls into boxes
        
(Message started by: mistaken_id on Mar 8^th, 2009, 5:30pm)

Title: Balls into boxes
Post by mistaken_id on Mar 8^th, 2009, 5:30pm

Suppose you have three boxes and n balls (numbered 1 to n on them) .

How many can you put balls into the three boxes, when the order in which balls are put into boxes also matters.

Edit*****************

Order here means that when a box contains two balls those two balls in the box can be arranged 2! ways.

Edit****************

Title: Re: Balls into boxes
Post by ThudanBlunder on Mar 8^th, 2009, 6:16pm

Does every box need to contain a ball?
If not, then in n!*3ⁿ ways.
Otherwise, in n!*S(n,3) (http://en.wikipedia.org/wiki/Stirling_number#Stirling_numbers_of_the_second_kind) ways.
And multiply by 3! if the boxes are ordered.

Title: Re: Balls into boxes
Post by mistaken_id on Mar 8^th, 2009, 6:33pm

Every box doesnt need to have a ball.

But how is it n!*3^n in that case......

Shouldnt we compute permutations of the individual boxes.... If b1 contains a1 balls and b2 contains a2 and b3 contains a3.......Shouldnt it be a function of a1!*a2!*a3!

Title: Re: Balls into boxes
Post by ThudanBlunder on Mar 8^th, 2009, 7:21pm

Firstly, consider the balls to be unordered (indistinguishable). That is, their order doesn't matter.
Now,
the 1st ball can go in any of 3 boxes...... so 1 ball can be placed in the 3 boxes in 3 ways.
the 2nd ball can go in any of 3 boxes..... so 2 balls can be placed in the 3 boxes in 3² ways.
the 3rd ball can go in any of 3 boxes...... so 3 balls can be placed in the 3 boxes in 3³ ways.
.............................................................................................................................
.............................................................................................................................
the nth ball can go in any of 3 boxes...... so n balls can be placed in the 3 boxes in 3ⁿ ways.

But that is just for one ordering of the balls.
They can be ordered beforehand in n! ways.
So total number of ways is n!*3ⁿ. OK?
If the boxes are also ordered (distinguishable) then we get 3!*n!*3ⁿ ways.

Title: Re: Balls into boxes
Post by mistaken_id on Mar 8^th, 2009, 7:45pm

But there will be repititions in n!*3^n.

Consider when you have only two balls.....Above equation gives us 18.

But I dont think there are so many unique ways

Title: Re: Balls into boxes
Post by mistaken_id on Mar 8^th, 2009, 8:11pm

Quote:

But that is just for one ordering of the balls.
They can be ordered beforehand in n! ways.

This will give to some repititions.......consider the case where you have two balls....

Order first using ball 1 (b1)

you may get one of these possibilities

-- b1 b2

Later order using ball 2 (b2)

you may get one of these possibilities

-- b1 b2.

which are same........

i think it should be strictly less than n!*3^n

Title: Re: Balls into boxes
Post by towr on Mar 9^th, 2009, 3:27am

on 03/08/09 at 19:45:58, mistaken_id wrote:

But there will be repititions in n!*3^n.

Consider when you have only two balls.....Above equation gives us 18.

But I dont think there are so many unique ways

There are:

first put the first ball in first box, then the second ball in first box
first put the first ball in first box, then the second ball in second box
first put the first ball in first box, then the second ball in third box
first put the first ball in second box, then the second ball in first box
first put the first ball in second box, then the second ball in second box
first put the first ball in second box, then the second ball in third box
first put the first ball in third box, then the second ball in first box
first put the first ball in third box, then the second ball in second box
first put the first ball in third box, then the second ball in third box
first put the second ball in first box, then the first ball in first box
first put the second ball in first box, then the first ball in second box
first put the second ball in first box, then the first ball in third box
first put the second ball in second box, then the first ball in first box
first put the second ball in second box, then the first ball in second box
first put the second ball in second box, then the first ball in third box
first put the second ball in third box, then the first ball in first box
first put the second ball in third box, then the first ball in second box
first put the second ball in third box, then the first ball in third box

These are all distinct ways of putting the two balls in the three boxes.
But, are you interested in, a) how many ways you can put the balls in the boxes, or b) how many ways you can find the balls in the boxes after they have been put there?

Title: Re: Balls into boxes
Post by towr on Mar 9^th, 2009, 3:33am

on 03/08/09 at 20:11:58, mistaken_id wrote:

It seems you don't care about the order of the balls, either in what order they were assigned to boxes, nor in the order in which they end up in boxes.
In which case, (N+X-1)!/(X-1)!/N! might be the answer you're looking for. (Where N is the number of balls, and X the number of boxes)

(3+2-1)!/(3-1)!/2!=24/2/2=6 ways, namely:
2,0,0 (i.e. two balls in the first box, none in the other two)
1,1,0
1,0,1
0,2,0
0,1,1
0,0,2

If this also isn't what you meant, I suggest you write out all the possible ways that you want to count.

Title: Re: Balls into boxes
Post by mistaken_id on Mar 9^th, 2009, 8:18am

Assume you have three boxes and 2 balls (b1 and b2).

When the order of the balls in the BOX DOESNT MATTER you have 3^2=9 possibilites.

(__, (b1),(b2))...box 1 doesnt contain anything..box 2 contains b1 and box 3 contains b2

(__, (b2),(b1))

((b1),__, (b2))

((b2),__, (b1))

((b1),(b2), (__))

((b2),(b1), (__))

((b1,b2), __,___)/** Two balls in Box1**/

( __,(b1,b2),___)

(__,__(b1,b2))

So you have 9 possibilites......

But when the ORDER OF THE BALLS IN THE BOX MATTERS....you have

(__, (b1),(b2))...box 1 doesnt contain anything..box 2 contains b1 and box 3 contains b2

(__, (b2),(b1))

((b1),__, (b2))

((b2),__, (b1))

((b1),(b2), (__))

((b2),(b1), (__))

((b1,b2), __,___)/** Two balls in Box1**/
((b2,b1), __,___)

( __,(b1,b2),___)
( __,(b2,b1),___)

(__,__(b1,b2))
(__,__(b2,b1))

So you have twelve possibilites with balls =2 and boxes = 3.

How can we generalize it to balls = n and boxes =3

Title: Re: Balls into boxes
Post by mistaken_id on Mar 9^th, 2009, 8:23am

This was the reason why I was saying that it will definitely be less than 3^n*n!..

In the above example it is 12 and not 18.

Hope the question is clear now

Title: Re: Balls into boxes
Post by towr on Mar 9^th, 2009, 10:24am

In that case, I'd say it's (N+X-1)!/(X-1)!
You can consider this as placing X-1 separators among the N balls.