Author |
Topic: Balls into boxes (Read 614 times) |
|
mistaken_id
Junior Member
Posts: 132
|
 |
Balls into boxes
« on: Mar 8th, 2009, 5:30pm » |
 Quote  Modify
|
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****************
|
| « Last Edit: Mar 8th, 2009, 9:49pm by mistaken_id » |
 IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
|
Re: Balls into boxes
« Reply #1 on: Mar 8th, 2009, 6:16pm » |
Quote Modify
|
Does every box need to contain a ball?
If not, then in n!*3n ways.
Otherwise, in n!*S(n,3) ways.
And multiply by 3! if the boxes are ordered.
|
| « Last Edit: Mar 9th, 2009, 6:55am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: Balls into boxes
« Reply #2 on: Mar 8th, 2009, 6:33pm » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Balls into boxes
« Reply #3 on: Mar 8th, 2009, 7:21pm » |
Quote Modify
|
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 32 ways.
the 3rd ball can go in any of 3 boxes...... so 3 balls can be placed in the 3 boxes in 33 ways.
........................................................................ .....................................................
........................................................................ .....................................................
the nth ball can go in any of 3 boxes...... so n balls can be placed in the 3 boxes in 3n 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!*3n. OK?
If the boxes are also ordered (distinguishable) then we get 3!*n!*3n ways.
|
| « Last Edit: Mar 8th, 2009, 7:22pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: Balls into boxes
« Reply #4 on: Mar 8th, 2009, 7:45pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: Balls into boxes
« Reply #5 on: Mar 8th, 2009, 8:11pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Balls into boxes
« Reply #6 on: Mar 9th, 2009, 3:27am » |
Quote Modify
|
on Mar 8th, 2009, 7:45pm, 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?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Balls into boxes
« Reply #7 on: Mar 9th, 2009, 3:33am » |
Quote Modify
|
on Mar 8th, 2009, 8:11pm, mistaken_id wrote:
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 |
|
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.
|
| « Last Edit: Mar 9th, 2009, 3:37am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: Balls into boxes
« Reply #8 on: Mar 9th, 2009, 8:18am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: Balls into boxes
« Reply #9 on: Mar 9th, 2009, 8:23am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Balls into boxes
« Reply #10 on: Mar 9th, 2009, 10:24am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print