1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Set partitioning

  1. Jul 23, 2006 #1
    I have another combinatorics problem:
    find the number of ways in which 5 different jobs can be assigned to 3 identical processors so that each processor gets at least 1 job.

    So, I am thinking that it is partitioning a set of 5 into 3 blocks, which would be S(5,3), is that correct? or am I missing something?
  2. jcsd
  3. Jul 23, 2006 #2
    There should be 60 combinations.
    Last edited: Jul 23, 2006
  4. Jul 23, 2006 #3
    the sequence of assigning the job does matter and once assigned you can't assign the job again, so we search for n out of k permutations:

    [tex]\frac {n!} {(n-k)!} = \frac {5!} {2!} = 5 * 4 * 3 = 60[/tex]
    Last edited: Jul 23, 2006
  5. Jul 23, 2006 #4


    User Avatar
    Science Advisor

    No, the answer is not 60. It is S(5, 3), where S(a, b) are the stirling numbers of the second kind. You don't permute this because the processors are identical.
    Last edited: Jul 23, 2006
  6. Jul 23, 2006 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I can't help, but I can ask if I know how to do it:

    Not knowing what S(a, b) means, there is a way to do this:

    First, one job is assigned to each computer (5C3). Then, you have two jobs to assign to three computers, so there are 6 ways of doing that. Multiply, and you're done.

    Wait.... but then you'll have repeats of different computers doing the same set of jobs, so you'll actually need to divide by.... the 6 ways of assigning each unique partition amongst the computers. So is the final answer 5C3, or did I miss something?
    Last edited: Jul 23, 2006
  7. Jul 23, 2006 #6


    User Avatar
    Science Advisor

    I don't know what you mean by this

    S(5, 3) = 25
  8. Jul 24, 2006 #7
    no it's not 6. If we calculate combinations here we are assuming this is a drawing experiment without laying back where the sequence doesn't matter.

    Assume we have a set ABCDE. We can recombine these letters


    These are 7 permutations, but 1 combination.

    Now we have 5 different jobs that must be distributed over 3 profs so that each gets 1 job. In how many ways is this possible ?

    We translate this to a drawing experiment. For the first professor 5 jobs can be assigned. The second prof has a choice of 4 (since 1 has been given away) and the third has a choice of 3 jobs.

    --> so the amount of possible designations of jobs to these 3 profs is 5 * 4 * 3 = 60 ways.

    If we say that prof 1 gets job A, prof 2 gets job B and prof 3 gets job C then according the definition of a combination the sequence prof 1 gets job C, prof 2 gets job A and prof 3 gets job B is the same.
    Last edited: Jul 24, 2006
  9. Jul 24, 2006 #8


    User Avatar
    Science Advisor

    The answer is S(5, 3) = 25 as the OP said. It is not 60. In fact the assignments can easily be enumerated by hand in a few minutes. Colons separate the processors:
  10. Jul 24, 2006 #9
    What about 5:14:23 and 2:34:15 and all the others you missed?

    Of course, you are wrong but you did realize something that I did not. That is the problem states "at least 1 job" meaning after giving all 3 processors 1 job that the other two jobs are assigned in a variety of ways. In essence, 60 combinations is wrong as well. It is in fact, it is a number much bigger than that.
    Last edited: Jul 24, 2006
  11. Jul 24, 2006 #10


    User Avatar
    Science Advisor

    5:14:23 is equivalent to 5:23:41 which is on the list. 2:34:15 is equivalent to 2:15:34 which is on the list. Remember the processors are considered identical (though if they weren't, 150 would be the correct answer, not 60).
  12. Jul 24, 2006 #11
    I don't believe that is correct. You have 3 identical processors, one in San Diego, one in NY and one in Austin. Sending the jobs 1 and 4 to San Diego, jobs 2 and 3 to NY and job 5 to Austin is not the same permutation as sending job 5 to Austin, jobs 1 and 4 to NY and jobs 2 and 3 to San Diego.

    We are in fact talking about the ways to assign these jobs.
    Last edited: Jul 24, 2006
  13. Jul 24, 2006 #12


    User Avatar
    Science Advisor

    If one was in San Diego, one in NY, and one in Austin, that means they wouldn't be considered identical. When things are called "identical" in combinatorics it is code for "consider permutations of these things to be the same." They wouldn't bother saying "identical" if it meant anything else.
  14. Jul 24, 2006 #13
    It is code huh? Well that's a new one to me.
    Last edited: Jul 24, 2006
  15. Jul 24, 2006 #14


    User Avatar
    Science Advisor

    I doubt it's that new. I'm sure you've seen questions asking you how many ways there are to place n identical books on k distinct shelves. The word is no different here.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook