There are r tasks that can be assigned to n people, where there is no limit on the number of tasks that can be assigned to each person.

Question

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!

Answer 1

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.