1
$\begingroup$

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.

  1. "Person number 1 is assigned no jobs";
  2. "People number 1 and 2 are assigned no jobs";
  3. "exactly two of the people are assigned no jobs"
  4. "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!

$\endgroup$

marked as duplicate by N. F. Taussig combinatorics 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
1
$\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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.