Discrete Math: In how many ways can 30 ident. balls be put in 7 distinct boxes, s.t.

sita

New member
Joined
Oct 27, 2017
Messages
36
1. In how many ways can 30 identical balls be distributed into 7 distinct boxes (numbered "Box 1, Box 2, ..., Box 7") subject to the following conditions?

(a) With no constraints.

(b) Each box gets at least three balls.

(c) Each of the odd-numbered boxes gets exactly one ball, and each of the even-numbered boxes gets at least one ball.

(d) Each box gets an even number of balls.




For the 1st one i get 36C6 is this correct?
 
Last edited by a moderator:

ksdhart2

Full Member
Joined
Mar 25, 2016
Messages
964
It's not immediately obvious what you mean by "1st one," but I'll guess that you probably mean part (1a). Assuming that's the case, your proposed answer is not correct. Since you've not shown any work or reasoning for how you arrived at your answer, I cannot be certain, but it looks to me like you're treating the rules and formulas you've learned in class as mystical, magical "black boxes." That is, you're trying to using them despite not really understanding what they mean or what they're doing.

Let's take a step back and consider what we mean when we say 36C6. It is typically read aloud as "36 choose 6," which right away clues us in that this is the number of ways we can choose 6 objects from a collection of 36. In the context of the problem, what are the 36 objects you're choosing from? Why are you choosing 6 from that collection? So now you might ask yourself: Does my answer make sense for the problem?

Instead, we can think of it in a different way. We have 30 balls to assign to 7 boxes. For now let's focus only on just the first ball. We can assign this ball to any of the seven boxes, so clearly there's 7 possible arrangements for one ball. But what if we added a second ball to play with? Well now we can assign each of them individually to any of the seven boxes. In other words, we can assign the first ball to any of the seven boxes, and then regardless of which box we choose (this is the important part here), we can assign the second ball to any of the seven boxes. That means there are 49 possible arrangements for two balls. Do you see why? What would happen if you had three balls? Four? How does this scale up to give you insight into the full problem with 30 balls?
 

sita

New member
Joined
Oct 27, 2017
Messages
36
It's not immediately obvious what you mean by "1st one," but I'll guess that you probably mean part (1a). Assuming that's the case, your proposed answer is not correct. Since you've not shown any work or reasoning for how you arrived at your answer, I cannot be certain, but it looks to me like you're treating the rules and formulas you've learned in class as mystical, magical "black boxes." That is, you're trying to using them despite not really understanding what they mean or what they're doing.

Let's take a step back and consider what we mean when we say 36C6. It is typically read aloud as "36 choose 6," which right away clues us in that this is the number of ways we can choose 6 objects from a collection of 36. In the context of the problem, what are the 36 objects you're choosing from? Why are you choosing 6 from that collection? So now you might ask yourself: Does my answer make sense for the problem?

Instead, we can think of it in a different way. We have 30 balls to assign to 7 boxes. For now let's focus only on just the first ball. We can assign this ball to any of the seven boxes, so clearly there's 7 possible arrangements for one ball. But what if we added a second ball to play with? Well now we can assign each of them individually to any of the seven boxes. In other words, we can assign the first ball to any of the seven boxes, and then regardless of which box we choose (this is the important part here), we can assign the second ball to any of the seven boxes. That means there are 49 possible arrangements for two balls. Do you see why? What would happen if you had three balls? Four? How does this scale up to give you insight into the full problem with 30 balls?
Please could you tell me where i've gone wrong, i did mean part (a)

 

j-astron

Junior Member
Joined
Jan 10, 2018
Messages
181
Please could you tell me where i've gone wrong, i did mean part (a)
I think you did it exactly right! It's combination with repetition. ksdhart2 seems to be barking up the "permutation with repetition" tree, which doesn't make sense, since the balls are indistinguishable.
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,232
Please could you tell me where i've gone wrong, i did mean part (a)

My original answer was incorrect, and incorrect in an unhelpful way. I have replaced it with this acknowledgement.
 
Last edited:

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,232
I think you did it exactly right! It's combination with repetition. ksdhart2 seems to be barking up the "permutation with repetition" tree, which doesn't make sense, since the balls are indistinguishable.
To be sure, the balls are indistinguishable, but the boxes are distinguishable. If you place one ball at a time in a box, you have seven choices with respect to each ball.

EDIT: This is true, but unintentionally misleading. When the process is complete, all that matters is how many balls are in a particular box, not when the balls were placed in the box sequentially.
 
Last edited:

j-astron

Junior Member
Joined
Jan 10, 2018
Messages
181
You have made an entirely unjustified assumption, namely that each box must contain at least one ball. That is what your six dividers represent. To answer the problem as given, you need to consider that one or more boxes contain no balls.

With respect: what are you guys talking about? How has the OP assumed this?

In the diagram he/she has six sticks and 30 circles that can be laid out in a line in any order. He/she permutes them. That covers all possibilities: e.g. you could end up with a permutation where it's

| | | | | | all circles here

i.e. all 30 balls ended up in bin 7.

How many ways are there to permute six sticks and 30 circles? Well that's 36 objects, so that's 36!. However, all the circles are the same, you have to divide this answer by the number of ways of permuting them, which is 30!. Also, all the sticks are also identical (reordering them within a given permutation doesn't change the result), so you also have to divide the answer by the number of ways of reordering the sticks amongst themselves, which is 6! In the end, you end up with:

\(\displaystyle \dfrac{36!}{6!30!} \)

Oh, what do you know, this is exactly equal to \(\displaystyle _{36}C_6 \) :rolleyes:

Suppose it were 3 balls and 2 bins. That would give you one divider and 3 circles. How about I just draw every single permutation?

ooo |

oo | o

o | oo

| ooo

And using my reasoning, the answer would be given by \(\displaystyle _4C_1 = \frac{4!}{1!3!} = 4 \). Are there any cases in the above example that I haven't covered, that would be added by whatever your proposed solution is? EDIT: and is your proposed solution 2^3 ??
 
Last edited:

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,232
5 balls 3 boxes So I am guessing that this is a 2 divider problem and that you think the answer should be

\(\displaystyle \dbinom{5}{2} = \dfrac{5!}{2! * 3!} = \dfrac{5 * 4}{2} = 10.\)

5, 0, 0 1
0, 5, 0 2
0, 0, 5 3
4, 0, 1 4
4, 1, 0 5
0, 4, 1 6
1, 4, 0 7
0, 1, 4 8
1, 0, 4 9
3, 0, 2 10
3, 2, 0 11
0, 3, 2 12
2, 3, 0 13
0, 2, 3 14
2, 0, 3 15
3, 1, 1 16
1, 3, 1 17
1, 1, 3 18

18 is not 10.

Of course 18 is not 125 either. I am changing my first answer to say that it is wrong.

EDIT: See next two posts.
 
Last edited:

j-astron

Junior Member
Joined
Jan 10, 2018
Messages
181
5 balls 3 boxes So I am guessing that this is a 2 divider problem and that you think the answer should be

\(\displaystyle \dbinom{5}{2} = \dfrac{5!}{2! * 3!} = \dfrac{5 * 4}{2} = 10.\)

5, 0, 0 1
0, 5, 0 2
0, 0, 5 3
4, 0, 1 4
4, 1, 0 5
0, 4, 1 6
1, 4, 0 7
0, 1, 4 8
1, 0, 4 9
3, 0, 2 10
3, 2, 0 11
0, 3, 2 12
2, 3, 0 13
0, 2, 3 14
2, 0, 3 15
3, 1, 1 16
1, 3, 1 17
1, 1, 3 18

18 is not 10.

Of course 18 is not 125 either. I am changing my first answer to say that it is wrong.
I think the answer should be (7 choose 2)

http://www.cs.sfu.ca/~ggbaker/zju/math/perm-comb-more.html#rep-comb
 

j-astron

Junior Member
Joined
Jan 10, 2018
Messages
181
JeffM: for the 5 ball, 3 box version, I think you forgot

2,2,1
2,1,2
1,2,2

18 + 3 = 21 = (7 choose 2)
 

ksdhart2

Full Member
Joined
Mar 25, 2016
Messages
964
Oh dear. I seem to have majorly messed up here. Sorry about that. Upon further reflection I see now that my proposed solution of 730 would only be valid if the balls were in some way distinguishable from one another (like if, say, they were numbered). However, that's not the case in this problem. I agree with the others that sita's solution of 36C6 is correct. Again, I do sincerely apologize for my mistake. I hope I didn't sow too much confusion.
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,232
JeffM: for the 5 ball, 3 box version, I think you forgot

2,2,1
2,1,2
1,2,2

18 + 3 = 21 = (7 choose 2)
Yes I did. So that answer was wrong too. However, in that case, I shall not delete it because that would leave your correcting post without context.
 

stapel

Super Moderator
Staff member
Joined
Feb 4, 2004
Messages
15,943
A bit off-topic, but:

I want to say a big "Thank you!" to all responders in this thread for being clear and complete, for kindly suggesting corrections, and for honorably admitting errors. This decent kind of give-and-take is a big part of what makes this forum so enjoyable and helpful! Again, thank you! ;)
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,232
A bit off-topic, but:

I want to say a big "Thank you!" to all responders in this thread for being clear and complete, for kindly suggesting corrections, and for honorably admitting errors. This decent kind of give-and-take is a big part of what makes this forum so enjoyable and helpful! Again, thank you! ;)
I truly appreciate your kind words. Of course I wish that I had not needed to be one to admit that my answers were completely insane. But my wife says that I should be grateful for my rare moments of sanity.
 
Top