set partitioning

EvLer

Hello,
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?
Thanks...

buddyholly9999

There should be 60 combinations.

sdekivit

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]

0rthodontist

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.

Office_Shredder

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?

0rthodontist

I don't know what you mean by this

S(5, 3) = 25

sdekivit

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

ABCDE, ACBDE, ABDCE, ABCED, CABDE, DABCE and EABCD and so on.

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.

0rthodontist

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:
1:2:345
1:3:245
1:4:235
1:5:234
2:3:145
2:4:135
2:5:134
3:4:125
3:5:124
4:5:123
1:23:45
1:24:35
1:25:34
2:13:45
2:14:35
2:15:34
3:21:45
3:24:15
3:25:14
4:23:15
4:21:35
4:25:31
5:23:41
5:24:31
5:21:34

buddyholly9999

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.

0rthodontist

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).

buddyholly9999

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.

0rthodontist

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.

buddyholly9999

It is code huh? Well that's a new one to me.

0rthodontist

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.