Page 1 of 2 12 LastLast
Results 1 to 10 of 14

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

  1. #1
    New Member
    Join Date
    Oct 2017
    Posts
    24

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

    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 stapel; 02-27-2018 at 06:40 PM. Reason: Typing out the text in the graphic; creating useful subject line.

  2. #2
    Full Member
    Join Date
    Mar 2016
    Posts
    916
    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?

  3. #3
    New Member
    Join Date
    Oct 2017
    Posts
    24
    Quote Originally Posted by ksdhart2 View Post
    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)


  4. #4
    Junior Member
    Join Date
    Jan 2018
    Location
    Toronto
    Posts
    181
    Quote Originally Posted by sita View Post
    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.

  5. #5
    Elite Member
    Join Date
    Sep 2012
    Posts
    3,033
    Quote Originally Posted by sita View Post
    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 by JeffM; 02-27-2018 at 05:14 PM.

  6. #6
    Elite Member
    Join Date
    Sep 2012
    Posts
    3,033
    Quote Originally Posted by j-astron View Post
    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 by JeffM; 02-28-2018 at 07:15 AM.

  7. #7
    Junior Member
    Join Date
    Jan 2018
    Location
    Toronto
    Posts
    181
    Quote Originally Posted by JeffM View Post
    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:

    [tex] \dfrac{36!}{6!30!} [/tex]

    Oh, what do you know, this is exactly equal to [tex] _{36}C_6 [/tex]

    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 [tex]_4C_1 = \frac{4!}{1!3!} = 4 [/tex]. 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 by j-astron; 02-26-2018 at 10:43 PM.

  8. #8
    Elite Member
    Join Date
    Sep 2012
    Posts
    3,033
    5 balls 3 boxes So I am guessing that this is a 2 divider problem and that you think the answer should be

    [tex]\dbinom{5}{2} = \dfrac{5!}{2! * 3!} = \dfrac{5 * 4}{2} = 10.[/tex]

    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 by JeffM; 02-28-2018 at 07:34 AM.

  9. #9
    Junior Member
    Join Date
    Jan 2018
    Location
    Toronto
    Posts
    181
    Quote Originally Posted by JeffM View Post
    5 balls 3 boxes So I am guessing that this is a 2 divider problem and that you think the answer should be

    [tex]\dbinom{5}{2} = \dfrac{5!}{2! * 3!} = \dfrac{5 * 4}{2} = 10.[/tex]

    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/ma....html#rep-comb

  10. #10
    Junior Member
    Join Date
    Jan 2018
    Location
    Toronto
    Posts
    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)

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •