Balls into Boxes Permutation Help

[Cyphin]

Homework Statement

Determine all possible ways to placing three balls into three boxes, where there may be more than one ball in anyone of the three boxes. Could you determine all possible ways of placing 20 balls in 365 boxes?

Homework Equations

The Attempt at a Solution

I know this problem requires a permutation but I just can't get it any help is greatly appreciated.

For instance from what I've tried I have (3 choose 1)*(3 choose 1)*(3 choose 1) = 27 combinations but I've been told this is incorrect.

 

[jbunniii]

The answer depends on whether the balls are distinguishable from one another (e.g., labeled or different colors) or not.

If the balls are labeled, then each ball can go in any of the three boxes, and all of these configurations are distinguishable, so there are 3*3*3 = 27 possibilities.

If the balls are not labeled, then some of the configurations look identical to one another. For example, if each box gets one ball, then you only count this once, whereas there are six ways to achieve this if the balls are labeled.

 

[Cyphin]

The answer depends on whether the balls are distinguishable from one another (e.g., labeled or different colors) or not.

If the balls are labeled, then each ball can go in any of the three boxes, and all of these configurations are distinguishable, so there are 3*3*3 = 27 possibilities.

If the balls are not labeled, then some of the configurations look identical to one another. For example, if each box gets one ball, then you only count this once, whereas there are six ways to achieve this if the balls are labeled.

Yes the balls are identical and so are the boxes see I got 27 combinations but I just can't wrap my head around a permutation or am I going in the wrong direction completely here?

 

[jbunniii]

Yes the balls are identical and so are the boxes see I got 27 combinations but I just can't wrap my head around a permutation or am I going in the wrong direction completely here?

When there are only three balls and three boxes, you can list all of the possibilities. The notation I am using below is

#balls in box 1, #balls in box 2, #balls in box 3

3,0,0
0,3,0
0,0,3
2,1,0
2,0,1
1,2,0
0,2,1
1,0,2
0,1,2
1,1,1

So there are ten possibilities.

Of course, this becomes impractical for much larger numbers. So your job is to find a formula.

Hint: it's of the form [tex]{n \choose k}[/tex]. What are [itex]n[/itex] and [itex]k[/itex]?

 

[Cyphin]

When there are only three balls and three boxes, you can list all of the possibilities. The notation I am using below is

#balls in box 1, #balls in box 2, #balls in box 3

3,0,0
0,3,0
0,0,3
2,1,0
2,0,1
1,2,0
0,2,1
1,0,2
0,1,2
1,1,1

So there are ten possibilities.

Of course, this becomes impractical for much larger numbers. So your job is to find a formula.

Hint: it's of the form [tex]{n \choose k}[/tex]. What are [itex]n[/itex] and [itex]k[/itex]?

N is the number of objects, K is the boxes? Am I correct?

 

[jbunniii]

N is the number of objects, K is the boxes? Am I correct?

Well, if that were the case, then in your example, N = 3 and K = 3.

What is [tex]{3 \choose 3}[/tex]? If it is not 10, then it can't be right.

 

[Cyphin]

Well, if that were the case, then in your example, N = 3 and K = 3.

What is [tex]{3 \choose 3}[/tex]? If it is not 10, then it can't be right.

No (3 choose 2) would be 1.

From what I can tell I need (5 choose 3) would equal 10 which is what I would be looking for if I'm correct?

Which would mean I would need ( n + k -1 choose k)?

 

[jbunniii]

No (3 choose 2) would be 1.

From what I can tell I need (5 choose 3) would equal 10 which is what I would be looking for if I'm correct?

Which would mean I would need ( n + k -1 choose k)?

Yes, that's correct. Can you come up with an explanation for why that's the right formula? ("It works when n = 3 and k = 3" isn't good enough! :-)

P.S. (3 choose 2) is 3, not 1. But I think you meant (3 choose 3).

 

[Cyphin]

Yes, that's correct. Can you come up with an explanation for why that's the right formula? ("It works when n = 3 and k = 3" isn't good enough! :-)

P.S. (3 choose 2) is 3, not 1. But I think you meant (3 choose 3).

Okay, so you have k elements plus n things - 1 which infers that the total number of things and ways to choose these things is subtracted by 1 because we know we need at least one element in one of the boxes divided by the number of ways n be chosen from the set of k things.

Is that somewhere in the ball park?

 

[jbunniii]

Okay, so you have k elements plus n things - 1 which infers that the total number of things and ways to choose these things is subtracted by 1 because we know we need at least one element in one of the boxes divided by the number of ways n be chosen from the set of k things.

Is that somewhere in the ball park?

I'm not sure I understood your argument.

Here is the one that seems the most straightforward to me:

Let's say you have 3 balls to distribute among 3 boxes. Instead of thinking about boxes, think about dividers between boxes. If I use the symbol | to represent a divider, and * to represent a ball, then I can distribute the following objects in any order:

***|| (all 3 balls in box #1)
**|*| (2 balls in box 1, 1 ball in box 2, none in box 3)
**||* (2 balls in box 1, 1 ball in box 3, none in box 2)
*|*|* (1 ball in each box)

and so on.

So now the question becomes: how many ways are there to place the three *'s in any of five positions? Thus (5 choose 3).

Equivalently, how many ways are there to place the two |'s in any of five positions? Thus (5 choose 2).

Oh no, both arguments seem valid but I got two different answers? Nope, because (5 choose 2) equals (5 choose 3).

You can easily generalize this to N balls and K boxes. If there are K boxes then there are K-1 dividers between them, so that's why you end up with N+K-1 choose N [or N+K-1 choose K-1, which is the same number].

 

[Cyphin]

I'm not sure I understood your argument.

Here is the one that seems the most straightforward to me:

Let's say you have 3 balls to distribute among 3 boxes. Instead of thinking about boxes, think about dividers between boxes. If I use the symbol | to represent a divider, and * to represent a ball, then I can distribute the following objects in any order:

***|| (all 3 balls in box #1)
**|*| (2 balls in box 1, 1 ball in box 2, none in box 3)
**||* (2 balls in box 1, 1 ball in box 3, none in box 2)
*|*|* (1 ball in each box)

and so on.

So now the question becomes: how many ways are there to place the three *'s in any of five positions? Thus (5 choose 3).

Equivalently, how many ways are there to place the two |'s in any of five positions? Thus (5 choose 2).

Oh no, both arguments seem valid but I got two different answers? Nope, because (5 choose 2) equals (5 choose 3).

You can easily generalize this to N balls and K boxes. If there are K boxes then there are K-1 dividers between them, so that's why you end up with N+K-1 choose N [or N+K-1 choose K-1, which is the same number].

Wow that actually makes complete sense when represented in that way. But what I've been trying to figure out is how to account for having at least 1 ball in one box how is this accounted for in that permutation? For instance if we were to have at least 2 balls in any box would that change the permutation(I know it couldn't be (n + k -2 choose k )? What I want to understand is how I can derive a permutation off off ( n choose k ) without having to manually draw out all combinations. Is there a short cut to breaking a problem down that way or do you always need to be able to visualize a smaller sample size to determine the combinations then form the permutation for larger quantities?

 

[jbunniii]

Wow that actually makes complete sense when represented in that way. But what I've been trying to figure out is how to account for having at least 1 ball in one box how is this accounted for in that permutation? For instance if we were to have at least 2 balls in any box would that change the permutation(I know it couldn't be (n + k -2 choose k )? What I want to understand is how I can derive a permutation off off ( n choose k ) without having to manually draw out all combinations. Is there a short cut to breaking a problem down that way or do you always need to be able to visualize a smaller sample size to determine the combinations then form the permutation for larger quantities?

Let me make sure I am understanding the question correctly. You want to know how many ways there are to put 3 balls into 3 boxes (or more generally, N balls into K boxes), with the constraint that at least one box gets at least two balls?

This is automatically true if there are more balls than boxes (pigeonhole principle).

So the interesting case is when N <= K.

If N = K, then the constraint (at least one box gets two or more balls) excludes only one arrangement, namely the one where each box gets exactly one ball. Therefore the number of arrangements in which at least one box gets 2 or more balls is (N+K-1 choose N) - 1.

If N < K, then the constraint excludes the arrangements where each box gets at most one ball. How many such arrangements are there? Well, it's the number of ways of choosing N out of K boxes, or (K choose N). Therefore, the number of arrangements where at least one box gets two or more balls is simply (N+K-1 choose N) - (K choose N). [Note that this formula works for the N=K case as well.]

Note: My reasoning above doesn't directly generalize to other constraints such as how to arrange N balls in K boxes where at least one box gets THREE or more balls.