Set Partitioning: Solving 5 Jobs to 3 Processors

  • Thread starter EvLer
  • Start date
  • Tags
    Set
In summary, 60 combinations is incorrect, it is S(5,3) where S(a, b) are the stirling numbers of the second kind.
  • #1
EvLer
458
0
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...
 
Physics news on Phys.org
  • #2
There should be 60 combinations.
 
Last edited:
  • #3
EvLer said:
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...

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:
  • #4
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:
  • #5
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:
  • #6
the 6 ways of assigning each unique partition amongst the computers
I don't know what you mean by this

S(5, 3) = 25
 
  • #7
EvLer said:
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...

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:
  • #8
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
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:
  • #10
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
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:
  • #12
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
When things are called "identical" in combinatorics it is code for "consider permutations of these things to be the same."

It is code huh? Well that's a new one to me.
 
Last edited:
  • #14
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.
 

1. What is set partitioning?

Set partitioning is a mathematical optimization technique used to divide a set of items into smaller subsets based on specific criteria. In the context of solving 5 jobs to 3 processors, it involves dividing a set of 5 jobs into 3 subsets, each of which can be assigned to a different processor.

2. How does set partitioning help solve the problem of assigning 5 jobs to 3 processors?

Set partitioning helps solve this problem by breaking down the set of 5 jobs into smaller subsets that can be easily assigned to individual processors. This ensures that each processor is assigned the appropriate workload, optimizing the overall efficiency and performance of the system.

3. What is the goal of set partitioning in this context?

The goal of set partitioning in this context is to minimize the total processing time of all 5 jobs by accurately assigning them to the 3 available processors. This helps optimize the overall performance of the system and ensures that no processor is overloaded while others remain underutilized.

4. How is set partitioning different from other optimization techniques?

Set partitioning is different from other optimization techniques, such as linear programming or integer programming, because it specifically focuses on dividing a set of items into smaller subsets. This makes it particularly useful for problems involving the allocation of resources or tasks to different entities.

5. What are some real-world applications of set partitioning?

Set partitioning has various real-world applications, including scheduling tasks on multiple processors, allocating resources to different projects, and optimizing inventory management. It can also be used in transportation planning, workforce scheduling, and other logistical problems where items need to be divided into smaller groups based on specific criteria.

Similar threads

Replies
5
Views
2K
  • Differential Equations
Replies
1
Views
658
  • Calculus and Beyond Homework Help
Replies
6
Views
859
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
689
  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
912
Replies
3
Views
1K
Back
Top