1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is there an efficient way to think of this combinatorial problem?

  1. Aug 22, 2012 #1
    1. The problem statement, all variables and given/known data
    prob-1.png

    Part (a). If the cards are distinct, I see an astronomical number of cases possible.

    Case 1. All 28 cards in one envelope. There are 9 envelopes. So 9 ways.

    Case 2. 27 of the 28 cards in one envelope. There are (28 choose 27) ways of selecting the 27 cards for one envelope. There are 9 envelopes possible. So (28 choose 27)*9. But then there's the one extra card to place in one of the eight other envelopes. There are 8 remaining envelopes. So in case 2, we have (28 choose 27)*9*8 ways.

    Case 3 gets REALLY complicated because you can have 26 cards in one envelope and 2 in a second envelope or 26 cards in one envelope, 1 in a second envelope, and 1 in a third envelope.

    So...(28 choose 26)*8 + (28 choose 26)*(2 choose 1)*(1 choose 1)*8*7


    See why I'm wondering if there's a more efficient way to do this?
     
  2. jcsd
  3. Aug 23, 2012 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Pick card 1. How many ways can you choose an envelope for it?
    After that is done, how many ways can you choose an envelope for card 2?
    etc...
     
  4. Aug 23, 2012 #3

    Bacle2

    User Avatar
    Science Advisor

    For the case (a) , I think this is your standard balls-in-boxes type of problem:

    The number of solutions to x1+x2+...+xn=k is :

    (n+k-1)C(k-1) if you allow for empty enveloppes (" n-1 choose k-1 ")

    or (n-1)C(k-1).
     
  5. Aug 23, 2012 #4
    You are right about the astronomical number of cases possible. However, just because it is astronomical doesn't mean you can't evaluate it.

    There is no limit on how many cards you can put in an envelope, so think this way: How many envelopes can you put the first card in? The second? The third? Then, you can use the general multiplication rule to multiply all those numbers to end up with the solution.
     
  6. Aug 23, 2012 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    In part (a) you need to clarify what constitutes "different ways". For example, if envelope 1 contains cards 1, 2 and 3, do you count 123 (in that order) as different from 321, etc? (Perhaps you look at the cards from front to back or something similar, so you can tell the difference between 123 and 321.) If you do count them as different, then: the first card to be placed can be any of the 28, and it can go into any of the 9 envelopes. Then the second card to be placed can be any of the remaining 27, and it can go into any of the 9 envelopes, etc. On the other hand, if the order within an envelope does not matter, the number of ways is the same whether or not the cards are distinct or identical. (If you don't believe this, compute both answers.)

    RGV
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Is there an efficient way to think of this combinatorial problem?
Loading...