Mixing
There are r tasks that can be assigned to n people, where there is no limit on the number of tasks that can...
$begingroup$
This question already has an answer here:
In dynamic resource allocation r tasks are assigned at random to n computers, with no restriction on the number of jobs per computer
1 answer
This is a hw question I got in my class, but I'm not even sure how to begin it. I need to find the probability of each of the four parts below, but first I can't even count the total number of ways these tasks could be allocated.
- "Person number 1 is assigned no jobs";
- "People number 1 and 2 are assigned no jobs";
- "exactly two of the people are assigned no jobs"
- "No person is assigned more than one job".
I wrote out some examples, and it has confused me even more.
For example, if we had 1 task and 2 people, all the possibilities are {(1,0), (0,1)}, giving 2 different possibilities.
If we had 2 tasks and 2 people, we have {(0,2), (1,1), (2,0)}, giving 3 different possibilities.
If we had 2 tasks and 3 people, we have {(2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1)}, giving 6.
I'm having a lot of difficulty with finding a pattern between these cases.
Any help would be appreciated. Thanks!
probability combinatorics permutations
edited Jan 17 at 22:06
N. F. Taussig
44.5k93357
asked Jan 17 at 21:24
Tim WeahTim Weah
865
$endgroup$
marked as duplicate by N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 17 at 23:59
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
In dynamic resource allocation r tasks are assigned at random to n computers, with no restriction on the number of jobs per computer
1 answer
This is a hw question I got in my class, but I'm not even sure how to begin it. I need to find the probability of each of the four parts below, but first I can't even count the total number of ways these tasks could be allocated.
- "Person number 1 is assigned no jobs";
- "People number 1 and 2 are assigned no jobs";
- "exactly two of the people are assigned no jobs"
- "No person is assigned more than one job".
I wrote out some examples, and it has confused me even more.
For example, if we had 1 task and 2 people, all the possibilities are {(1,0), (0,1)}, giving 2 different possibilities.
If we had 2 tasks and 2 people, we have {(0,2), (1,1), (2,0)}, giving 3 different possibilities.
If we had 2 tasks and 3 people, we have {(2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1)}, giving 6.
I'm having a lot of difficulty with finding a pattern between these cases.
Any help would be appreciated. Thanks!
probability combinatorics permutations
edited Jan 17 at 22:06
N. F. Taussig
44.5k93357
asked Jan 17 at 21:24
Tim WeahTim Weah
865
$endgroup$
marked as duplicate by N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 17 at 23:59
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
If you are asking a probability question, you need to specify how the assignment is randomly chosen. Is each task assigned to a uniformly random person, independent of the others?
$endgroup$
– Mike Earnest
Jan 17 at 22:56
$begingroup$
Yes, sorry. Each task is assigned to a uniformly random person, and independent of the others.
$endgroup$
– Tim Weah
Jan 17 at 22:59
$begingroup$
Also, this has already been asked: math.stackexchange.com/questions/3076435/…
$endgroup$
– Mike Earnest
Jan 17 at 23:18
$begingroup$
@TimWeah I upvoted because I thought that you showed good preliminary effort in solving the problem on your own.
$endgroup$
– user2661923
Jan 17 at 23:54
add a comment |
$begingroup$
This question already has an answer here:
In dynamic resource allocation r tasks are assigned at random to n computers, with no restriction on the number of jobs per computer
1 answer
This is a hw question I got in my class, but I'm not even sure how to begin it. I need to find the probability of each of the four parts below, but first I can't even count the total number of ways these tasks could be allocated.
- "Person number 1 is assigned no jobs";
- "People number 1 and 2 are assigned no jobs";
- "exactly two of the people are assigned no jobs"
- "No person is assigned more than one job".
I wrote out some examples, and it has confused me even more.
For example, if we had 1 task and 2 people, all the possibilities are {(1,0), (0,1)}, giving 2 different possibilities.
If we had 2 tasks and 2 people, we have {(0,2), (1,1), (2,0)}, giving 3 different possibilities.
If we had 2 tasks and 3 people, we have {(2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1)}, giving 6.
I'm having a lot of difficulty with finding a pattern between these cases.
Any help would be appreciated. Thanks!
probability combinatorics permutations
edited Jan 17 at 22:06
N. F. Taussig
44.5k93357
asked Jan 17 at 21:24
Tim WeahTim Weah
865
$endgroup$
This question already has an answer here:
In dynamic resource allocation r tasks are assigned at random to n computers, with no restriction on the number of jobs per computer
1 answer
This is a hw question I got in my class, but I'm not even sure how to begin it. I need to find the probability of each of the four parts below, but first I can't even count the total number of ways these tasks could be allocated.
- "Person number 1 is assigned no jobs";
- "People number 1 and 2 are assigned no jobs";
- "exactly two of the people are assigned no jobs"
- "No person is assigned more than one job".
I wrote out some examples, and it has confused me even more.
For example, if we had 1 task and 2 people, all the possibilities are {(1,0), (0,1)}, giving 2 different possibilities.
If we had 2 tasks and 2 people, we have {(0,2), (1,1), (2,0)}, giving 3 different possibilities.
If we had 2 tasks and 3 people, we have {(2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1)}, giving 6.
I'm having a lot of difficulty with finding a pattern between these cases.
Any help would be appreciated. Thanks!
This question already has an answer here:
In dynamic resource allocation r tasks are assigned at random to n computers, with no restriction on the number of jobs per computer
1 answer
probability combinatorics permutations
probability combinatorics permutations
edited Jan 17 at 22:06
N. F. Taussig
44.5k93357
asked Jan 17 at 21:24
Tim WeahTim Weah
865
edited Jan 17 at 22:06
N. F. Taussig
44.5k93357
asked Jan 17 at 21:24
Tim WeahTim Weah
865
edited Jan 17 at 22:06
N. F. Taussig
44.5k93357
edited Jan 17 at 22:06
N. F. Taussig
44.5k93357
edited Jan 17 at 22:06
N. F. Taussig
44.5k93357
44.5k93357
asked Jan 17 at 21:24
Tim WeahTim Weah
865
asked Jan 17 at 21:24
Tim WeahTim Weah
865
asked Jan 17 at 21:24
Tim WeahTim Weah
865
865
marked as duplicate by N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 17 at 23:59
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 17 at 23:59
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
If you are asking a probability question, you need to specify how the assignment is randomly chosen. Is each task assigned to a uniformly random person, independent of the others?
$endgroup$
– Mike Earnest
Jan 17 at 22:56
$begingroup$
Yes, sorry. Each task is assigned to a uniformly random person, and independent of the others.
$endgroup$
– Tim Weah
Jan 17 at 22:59
$begingroup$
Also, this has already been asked: math.stackexchange.com/questions/3076435/…
$endgroup$
– Mike Earnest
Jan 17 at 23:18
$begingroup$
@TimWeah I upvoted because I thought that you showed good preliminary effort in solving the problem on your own.
$endgroup$
– user2661923
Jan 17 at 23:54
add a comment |
$begingroup$
If you are asking a probability question, you need to specify how the assignment is randomly chosen. Is each task assigned to a uniformly random person, independent of the others?
$endgroup$
– Mike Earnest
Jan 17 at 22:56
$begingroup$
Yes, sorry. Each task is assigned to a uniformly random person, and independent of the others.
$endgroup$
– Tim Weah
Jan 17 at 22:59
$begingroup$
Also, this has already been asked: math.stackexchange.com/questions/3076435/…
$endgroup$
– Mike Earnest
Jan 17 at 23:18
$begingroup$
@TimWeah I upvoted because I thought that you showed good preliminary effort in solving the problem on your own.
$endgroup$
– user2661923
Jan 17 at 23:54
$begingroup$
If you are asking a probability question, you need to specify how the assignment is randomly chosen. Is each task assigned to a uniformly random person, independent of the others?
$endgroup$
– Mike Earnest
Jan 17 at 22:56
$begingroup$
If you are asking a probability question, you need to specify how the assignment is randomly chosen. Is each task assigned to a uniformly random person, independent of the others?
$endgroup$
– Mike Earnest
Jan 17 at 22:56
$begingroup$
Yes, sorry. Each task is assigned to a uniformly random person, and independent of the others.
$endgroup$
– Tim Weah
Jan 17 at 22:59
$begingroup$
Yes, sorry. Each task is assigned to a uniformly random person, and independent of the others.
$endgroup$
– Tim Weah
Jan 17 at 22:59
$begingroup$
Also, this has already been asked: math.stackexchange.com/questions/3076435/…
$endgroup$
– Mike Earnest
Jan 17 at 23:18
$begingroup$
Also, this has already been asked: math.stackexchange.com/questions/3076435/…
$endgroup$
– Mike Earnest
Jan 17 at 23:18
$begingroup$
@TimWeah I upvoted because I thought that you showed good preliminary effort in solving the problem on your own.
$endgroup$
– user2661923
Jan 17 at 23:54
$begingroup$
@TimWeah I upvoted because I thought that you showed good preliminary effort in solving the problem on your own.
$endgroup$
– user2661923
Jan 17 at 23:54
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There are $n$ possible ways to assign each of the $r$ tasks, so the sample space has $n^r$ possible assignments.
Suppose tasks $A$, $B$ can be assigned to persons $1$, $2$, or $3$. Then there are $3^2 = 9$ possible assignments, as shown in the following table, with each row corresponding to an assignment.
begin{array}{c c c}
1 & 2 & 3\ hline
A, B & & \
A & B & \
A & & B \
B & A & \
B & & A\
& A, B & \
& A & B \
& B & A \
& & B, A
end{array}
For the first question, since person number $1$ is not assigned a task, there are $n - 1$ ways to assign each of the $r$ tasks.
For the second question since persons $1$ and $2$ are not assigned a task, there are $n - 2$ ways to assign each of the $r$ tasks.
For the third question, choose which two people will not be assigned a task, then assign the $r$ tasks to the remaining $n - 2$ people. Since each of those $n - 2$ people must be assigned a task, the number of such assignments is equal to the number of surjective functions from a set of $r$ elements to a set of $n - 2$ elements, which is found by multiplying the Stirling number of the second kind $S(r, n - 2)$ by the $(n - 2)!$ ways of matching people to groups of tasks.
For the fourth question, choose which $r$ people will be assigned a task, then distribute the tasks to them.
answered Jan 17 at 22:15
N. F. TaussigN. F. Taussig
44.5k93357
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There are $n$ possible ways to assign each of the $r$ tasks, so the sample space has $n^r$ possible assignments.
Suppose tasks $A$, $B$ can be assigned to persons $1$, $2$, or $3$. Then there are $3^2 = 9$ possible assignments, as shown in the following table, with each row corresponding to an assignment.
begin{array}{c c c}
1 & 2 & 3\ hline
A, B & & \
A & B & \
A & & B \
B & A & \
B & & A\
& A, B & \
& A & B \
& B & A \
& & B, A
end{array}
For the first question, since person number $1$ is not assigned a task, there are $n - 1$ ways to assign each of the $r$ tasks.
For the second question since persons $1$ and $2$ are not assigned a task, there are $n - 2$ ways to assign each of the $r$ tasks.
For the third question, choose which two people will not be assigned a task, then assign the $r$ tasks to the remaining $n - 2$ people. Since each of those $n - 2$ people must be assigned a task, the number of such assignments is equal to the number of surjective functions from a set of $r$ elements to a set of $n - 2$ elements, which is found by multiplying the Stirling number of the second kind $S(r, n - 2)$ by the $(n - 2)!$ ways of matching people to groups of tasks.
For the fourth question, choose which $r$ people will be assigned a task, then distribute the tasks to them.
answered Jan 17 at 22:15
N. F. TaussigN. F. Taussig
44.5k93357
$endgroup$
add a comment |
$begingroup$
There are $n$ possible ways to assign each of the $r$ tasks, so the sample space has $n^r$ possible assignments.
Suppose tasks $A$, $B$ can be assigned to persons $1$, $2$, or $3$. Then there are $3^2 = 9$ possible assignments, as shown in the following table, with each row corresponding to an assignment.
begin{array}{c c c}
1 & 2 & 3\ hline
A, B & & \
A & B & \
A & & B \
B & A & \
B & & A\
& A, B & \
& A & B \
& B & A \
& & B, A
end{array}
For the first question, since person number $1$ is not assigned a task, there are $n - 1$ ways to assign each of the $r$ tasks.
For the second question since persons $1$ and $2$ are not assigned a task, there are $n - 2$ ways to assign each of the $r$ tasks.
For the third question, choose which two people will not be assigned a task, then assign the $r$ tasks to the remaining $n - 2$ people. Since each of those $n - 2$ people must be assigned a task, the number of such assignments is equal to the number of surjective functions from a set of $r$ elements to a set of $n - 2$ elements, which is found by multiplying the Stirling number of the second kind $S(r, n - 2)$ by the $(n - 2)!$ ways of matching people to groups of tasks.
For the fourth question, choose which $r$ people will be assigned a task, then distribute the tasks to them.
answered Jan 17 at 22:15
N. F. TaussigN. F. Taussig
44.5k93357
$endgroup$
add a comment |
$begingroup$
There are $n$ possible ways to assign each of the $r$ tasks, so the sample space has $n^r$ possible assignments.
Suppose tasks $A$, $B$ can be assigned to persons $1$, $2$, or $3$. Then there are $3^2 = 9$ possible assignments, as shown in the following table, with each row corresponding to an assignment.
begin{array}{c c c}
1 & 2 & 3\ hline
A, B & & \
A & B & \
A & & B \
B & A & \
B & & A\
& A, B & \
& A & B \
& B & A \
& & B, A
end{array}
For the first question, since person number $1$ is not assigned a task, there are $n - 1$ ways to assign each of the $r$ tasks.
For the second question since persons $1$ and $2$ are not assigned a task, there are $n - 2$ ways to assign each of the $r$ tasks.
For the third question, choose which two people will not be assigned a task, then assign the $r$ tasks to the remaining $n - 2$ people. Since each of those $n - 2$ people must be assigned a task, the number of such assignments is equal to the number of surjective functions from a set of $r$ elements to a set of $n - 2$ elements, which is found by multiplying the Stirling number of the second kind $S(r, n - 2)$ by the $(n - 2)!$ ways of matching people to groups of tasks.
For the fourth question, choose which $r$ people will be assigned a task, then distribute the tasks to them.
answered Jan 17 at 22:15
N. F. TaussigN. F. Taussig
44.5k93357
$endgroup$
There are $n$ possible ways to assign each of the $r$ tasks, so the sample space has $n^r$ possible assignments.
Suppose tasks $A$, $B$ can be assigned to persons $1$, $2$, or $3$. Then there are $3^2 = 9$ possible assignments, as shown in the following table, with each row corresponding to an assignment.
begin{array}{c c c}
1 & 2 & 3\ hline
A, B & & \
A & B & \
A & & B \
B & A & \
B & & A\
& A, B & \
& A & B \
& B & A \
& & B, A
end{array}
For the first question, since person number $1$ is not assigned a task, there are $n - 1$ ways to assign each of the $r$ tasks.
For the second question since persons $1$ and $2$ are not assigned a task, there are $n - 2$ ways to assign each of the $r$ tasks.
For the third question, choose which two people will not be assigned a task, then assign the $r$ tasks to the remaining $n - 2$ people. Since each of those $n - 2$ people must be assigned a task, the number of such assignments is equal to the number of surjective functions from a set of $r$ elements to a set of $n - 2$ elements, which is found by multiplying the Stirling number of the second kind $S(r, n - 2)$ by the $(n - 2)!$ ways of matching people to groups of tasks.
For the fourth question, choose which $r$ people will be assigned a task, then distribute the tasks to them.
answered Jan 17 at 22:15
N. F. TaussigN. F. Taussig
44.5k93357
edited Jan 17 at 22:44
answered Jan 17 at 22:15
N. F. TaussigN. F. Taussig
44.5k93357
answered Jan 17 at 22:15
N. F. TaussigN. F. Taussig
44.5k93357
answered Jan 17 at 22:15
N. F. TaussigN. F. Taussig
44.5k93357
44.5k93357
add a comment |
add a comment |
$begingroup$
If you are asking a probability question, you need to specify how the assignment is randomly chosen. Is each task assigned to a uniformly random person, independent of the others?
$endgroup$
– Mike Earnest
Jan 17 at 22:56
$begingroup$
Yes, sorry. Each task is assigned to a uniformly random person, and independent of the others.
$endgroup$
– Tim Weah
Jan 17 at 22:59
$begingroup$
Also, this has already been asked: math.stackexchange.com/questions/3076435/…
$endgroup$
– Mike Earnest
Jan 17 at 23:18
$begingroup$
@TimWeah I upvoted because I thought that you showed good preliminary effort in solving the problem on your own.
$endgroup$
– user2661923
Jan 17 at 23:54