# Set partitioning

1. Jul 23, 2006

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

2. Jul 23, 2006

### buddyholly9999

There should be 60 combinations.

Last edited: Jul 23, 2006
3. Jul 23, 2006

### 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:

$$\frac {n!} {(n-k)!} = \frac {5!} {2!} = 5 * 4 * 3 = 60$$

Last edited: Jul 23, 2006
4. Jul 23, 2006

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

Last edited: Jul 23, 2006
5. Jul 23, 2006

### Office_Shredder

Staff Emeritus
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
6. Jul 23, 2006

### 0rthodontist

I don't know what you mean by this

S(5, 3) = 25

7. Jul 24, 2006

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

Last edited: Jul 24, 2006
8. Jul 24, 2006

### 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

9. Jul 24, 2006

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

Last edited: Jul 24, 2006
10. Jul 24, 2006

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

11. Jul 24, 2006

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

Last edited: Jul 24, 2006
12. Jul 24, 2006

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

13. Jul 24, 2006

### buddyholly9999

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

Last edited: Jul 24, 2006
14. Jul 24, 2006

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